Exceptional Quantum Walk Search on the Cycle
arXiv:1610.06075 · doi:10.1007/s11128-017-1606-y
Abstract
Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk's hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk's random sampling yields an arbitrary speedup in query complexity over the classical random walk's hitting time. In this context, however, the mixing time to prepare the initial uniform state is a more suitable comparison than the hitting time, and then the speedup is roughly quadratic.
arXiv comment16 pages, 7 figures
References in corpus (15)
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- From quantum cellular automata to quantum lattice gases
- Search via Quantum Walk
- Faster quantum walk algorithm for the two dimensional spatial search
- On the absence of homogeneous scalar unitary cellular automata
- Quantum walks can find a marked element on any graph
- The Staggered Quantum Walk Model
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Quantum Search with Multiple Walk Steps per Oracle Query
- Equivalence of Szegedy's and Coined Quantum Walks
- Mixing Times in Quantum Walks on Two-Dimensional Grids
- Stationary States in Quantum Walk Search
- Full Characterization of Oscillatory Localization of Quantum Walks
- Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits
Cited by in corpus (6)
- Equivalence of Szegedy's and Coined Quantum Walks
- Quantum walk-based search algorithms with multiple marked vertices
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Generalized exceptional quantum walk search
- Quantum-walk search in motion
- On the probability of finding marked connected components using quantum walks