February 1, 2008 | Neil Shenvi1, Julia Kempe1,2,3, and K. Birgitta Whaley1
This paper presents a quantum search algorithm based on quantum random walks, which provides an algorithmic speed-up over classical algorithms. The algorithm is designed to perform an oracle search on a database of \( N \) items with \( O(\sqrt{N}) \) calls to the oracle, similar to other quantum search algorithms. The authors introduce a perturbation to the unitary evolution operator of a discrete-time quantum random walk, specifically by marking a single node with a special coin operation. This perturbation allows the algorithm to efficiently search for the marked node among \( 2^n \) nodes on an \( n \)-cube. The correctness of the algorithm is proven through a series of theorems, showing that the algorithm can be approximated by a two-dimensional rotation in a subspace spanned by two eigenvectors of the perturbed operator. The final state of the algorithm is a linear combination of states, primarily the marked state, but also containing contributions from its nearest and second-nearest neighbors. The paper also discusses the differences between the random walk search algorithm and Grover's algorithm, highlighting that the former is not exactly equivalent to the latter but shares similarities in their use of the Grover diffusion operator and oracle marking. The authors conclude that the quantum random walk provides a framework for developing new quantum algorithms and offers potential for further optimization and application to other regular graphs.This paper presents a quantum search algorithm based on quantum random walks, which provides an algorithmic speed-up over classical algorithms. The algorithm is designed to perform an oracle search on a database of \( N \) items with \( O(\sqrt{N}) \) calls to the oracle, similar to other quantum search algorithms. The authors introduce a perturbation to the unitary evolution operator of a discrete-time quantum random walk, specifically by marking a single node with a special coin operation. This perturbation allows the algorithm to efficiently search for the marked node among \( 2^n \) nodes on an \( n \)-cube. The correctness of the algorithm is proven through a series of theorems, showing that the algorithm can be approximated by a two-dimensional rotation in a subspace spanned by two eigenvectors of the perturbed operator. The final state of the algorithm is a linear combination of states, primarily the marked state, but also containing contributions from its nearest and second-nearest neighbors. The paper also discusses the differences between the random walk search algorithm and Grover's algorithm, highlighting that the former is not exactly equivalent to the latter but shares similarities in their use of the Grover diffusion operator and oracle marking. The authors conclude that the quantum random walk provides a framework for developing new quantum algorithms and offers potential for further optimization and application to other regular graphs.