Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
arXiv:2410.22011 · doi:10.1103/PhysRevA.111.032216
Abstract
This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.
RevTex 4.2, 19 pages, 12 color figures
References in corpus (25)
- Array Programming with NumPy
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Information and Computation: Classical and Quantum Aspects
- Quantum Circuits for General Multiqubit Gates
- Quantum walks in higher dimensions
- Quantum speedup for active learning agents
- The effects of mixedness and entanglement on the properties of the entropic uncertainty in Heisenberg model with Dzyaloshinski-Moriya interaction
- Quantum circuits with uniformly controlled one-qubit gates
- Google in a Quantum Network
- Quantum Google in a Complex Network
- Quantum walks can find a marked element on any graph
- The Staggered Quantum Walk Model
- Deterministic Grover search with a restricted oracle
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- Coined Quantum Walks on Weighted Graphs
- Efficient quantum circuits for Szegedy quantum walks
- Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
- Discrete-time Semiclassical Szegedy Quantum Walks
- SQUWALS: A Szegedy QUantum WALks Simulator
- Quantum Bayesian Inference with Renormalization for Gravitational Waves
- Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine