Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk

Abstract

We analyse the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a controlled spatial search algorithm with multiple target states, and determine the oracle complexity as a function of the spectral gap and the number of target states. The oracle complexity is optimal as a function of the graph size and the number of target states, when the spectral gap of the adjacency matrix is $\Theta (1)$. It is also optimal for spatial search on $D>4$ dimensional hypercubic lattices. Otherwise it matches the best result available in the literature, with a much simpler algorithm. Our results also yield bounds on the classical hitting time of random walks on regular graphs, which may be of independent interest.

arXiv comment37 pages (v2) Revised to use Tulsi's controlled spatial search algorithm. The oracle complexity is improved, and is optimal for D>4 hypercubic lattices. Results compared to those obtained in terms of hitting time

References in corpus (13)

• Quantum Amplitude Amplification and Estimation
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Search via Quantum Walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Quantum walks can find a marked element on any graph
• Quantum Random Walks do not need a Coin Toss
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Search on a Fractal Lattice using a Quantum Random Walk
• Equivalence of Szegedy's and Coined Quantum Walks
• General framework for quantum search algorithms
• Quantum Proofs for Classical Theorems

Cited by in corpus (4)

• Quantum walk-based search algorithms with multiple marked vertices
• Improving the query complexity of quantum spatial search in two dimensions
• A Complete Characterization of Pretty Good State Transfer on Paths
• Constant gap between conventional strategies and those based on C*-dynamics for self-embezzlement