Efficient quantum walk on the grid with multiple marked elements
arXiv:1612.08958 · doi:10.4230/LIPIcs.STACS.2017.42
Abstract
We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.
arXiv comment18 pages, to appear in STACS 2017, the 34th International Symposium on Theoretical Aspects of Computer Science
References in corpus (15)
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Quantum Algorithms Revisited
- Semiclassical Fourier Transform for Quantum Computation
- Search via Quantum Walk
- Faster quantum walk algorithm for the two dimensional spatial search
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum walks can find a marked element on any graph
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Spatial search by continuous-time quantum walks on crystal lattices
- On the adiabatic condition and the quantum hitting time of Markov chains
- Quantum walk based search algorithms
- Quantum Complexity of Testing Group Commutativity
- Search by quantum walks on two-dimensional grid without amplitude amplification
- A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates