Equivalence of Szegedy's and Coined Quantum Walks
arXiv:1611.02238 · doi:10.1007/s11128-017-1667-y
Abstract
Szegedy's quantum walk is a quantization of a classical random walk or Markov chain, where the walk occurs on the edges of the bipartite double cover of the original graph. To search, one can simply quantize a Markov chain with absorbing vertices. Recently, Santos proposed two alternative search algorithms that instead utilize the sign-flip oracle in Grover's algorithm rather than absorbing vertices. In this paper, we show that these two algorithms are exactly equivalent to two algorithms involving coined quantum walks, which are walks on the vertices of the original graph with an internal degree of freedom. The first scheme is equivalent to a coined quantum walk with one walk-step per query of Grover's oracle, and the second is equivalent to a coined quantum walk with two walk-steps per query of Grover's oracle. These equivalences lie outside the previously known equivalence of Szegedy's quantum walk with absorbing vertices and the coined quantum walk with the negative identity operator as the coin for marked vertices, whose precise relationships we also investigate.
arXiv comment15 pages, 3 figures
References in corpus (26)
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- From quantum cellular automata to quantum lattice gases
- Universal quantum computation using the discrete time quantum walk
- Universal computation by multi-particle quantum walk
- On the absence of homogeneous scalar unitary cellular automata
- Grover Search with Lackadaisical Quantum Walks
- Global Symmetry is Unnecessary for Fast Quantum Search
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Mixing Times in Quantum Walks on the Hypercube
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Quantum Search with Multiple Walk Steps per Oracle Query
- Quantum walk speedup of backtracking algorithms
- Quantum Walk Search on Johnson Graphs
- Mixing Times in Quantum Walks on Two-Dimensional Grids
- Stationary States in Quantum Walk Search
- Exceptional Quantum Walk Search on the Cycle
- Full Characterization of Oscillatory Localization of Quantum Walks
- Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits
- Coined Quantum Walks as Quantum Markov Chains
- Quantum Walks on Sierpinski Gaskets
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
- Quantum Walk Search through Potential Barriers
Cited by in corpus (17)
- Quantum walk approach to simulating parton showers
- Faster Search by Lackadaisical Quantum Walk
- Coined Quantum Walks on Weighted Graphs
- Exceptional Quantum Walk Search on the Cycle
- A counterintuitive role of geometry in transport by quantum walks
- Probability distributions for Markov chains based quantum walks
- Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
- Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
- Unstructured Search by Random and Quantum Walk
- Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs
- Improving the query complexity of quantum spatial search in two dimensions
- A Complete Characterization of Pretty Good State Transfer on Paths
- Quantum Walks on Embeddings
- Discrete-Time Quantum Walks and Graph Structures
- Effective simulation of state distribution in qubit chains
- Impact of the malicious input data modification on the efficiency of quantum spatial search
- Quantum Algorithm for Testing Graph Completeness