Unstructured Search by Random and Quantum Walk

Abstract

The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N\ln (1/\epsilon )$ time to reach a success probability of $1-\epsilon$. In contrast, the discrete-time quantum walk asymptotically takes $\pi \sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $\pi \sqrt{N}/2$ time to reach a success probability of $1$.

arXiv comment33 pages, 11 figures

References in corpus (13)

• Strengths and Weaknesses of Quantum Computing
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Spatial search by quantum walk is optimal for almost all graphs
• On the absence of homogeneous scalar unitary cellular automata
• Quantum walks based on an interferometric analogy
• Grover Search with Lackadaisical Quantum Walks
• Global Symmetry is Unnecessary for Fast Quantum Search
• Hamiltonian Oracles
• Equivalence of Szegedy's and Coined Quantum Walks
• Full Characterization of Oscillatory Localization of Quantum Walks
• Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits

Cited by in corpus (1)

• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids