Improving the query complexity of quantum spatial search in two dimensions
arXiv:1810.12600 · doi:10.26421/QIC19.7-8
Abstract
The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.
20 pages (v2) Published version. (v3) Normalisation error in Corollary 2 corrected, replacing 1/8 by 1/2. Corresponding changes by a factor of 4 occur in Eqs.(33-35) and (43-46). Results and conclusions remain unchanged
References in corpus (16)
- Quantum Amplitude Amplification and Estimation
- Quantum Communication Through an Unmodulated Spin Chain
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Exponential algorithmic speedup by quantum walk
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- Search via Quantum Walk
- Faster quantum walk algorithm for the two dimensional spatial search
- Number-Theoretic Nature of Communication in Quantum Spin Systems
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum walks can find a marked element on any graph
- Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
- Quantum Search with Multiple Walk Steps per Oracle Query
- Equivalence of Szegedy's and Coined Quantum Walks
- Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
- Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach