Coins Make Quantum Walks Faster

Abstract

We show how to search N items arranged on a $\sqrt{N}\times \sqrt{N}$ grid in time $O(\sqrt{N}\log N)$, using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom, since it has been shown recently that such a continuous time walk needs time $\Omega (N)$ to perform the same task. Our result furthermore improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of $O(\sqrt{N})$ and give several extensions of quantum walk search algorithms for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another ``natural'' choice of coin gives a walk that takes $\Omega (N)$ steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time $O(\sqrt{N}\log N)$.

25 pages, no figures

References in corpus (6)

• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Quantum walk algorithm for element distinctness
• Quantum Algorithms for the Triangle Problem

Cited by in corpus (6)

• Quantum Search on the Spatial Grid
• Entanglement entropy distinguishes PT-symmetry and topological phases in a class of non-unitary quantum walks
• Localization of space-inhomogeneous three-state quantum walks
• A Quantum Algorithm for the Sensitivity Analysis of Business Risks
• On Hitting Times for General Quantum Markov Processes
• The localization of quantum random walks on sierpinski gaskets