Quantum random-walk search algorithm

By N. Shenvi, Julia Kempe, K. Birgitta Whaley. 2002

980 citations recorded by the source corpus.

Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with $O(\sqrt{N})$ calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0f3cec85590c92be7fd01ad3182e9e1a6cbaa84e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Universal quantum computation using the discrete-time quantum walk (2009, background): “walker’s initial state is also important, unlike in the classical random walk. A good review of these eﬀects can be found in [27]. The quantum walk can easily be modiﬁed to become a search algorithm, [11]. By starting the walk in an equal superposition over all vertices, | ψinitiali = 1 √ dN XN x=0 ”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, methodology): “The algorithm of [10] If there is no marked items, then the algorithm stays in the starting state 1 P If there is a single marked vertex v x , then, running this algorithm for O ( √ N ) steps and measuring the state gives | x, i for the marked x and some i with high probability (cf. x,i | x i| i .”
Efficient Quantum Algorithms for Simulating Sparse Hamiltonians (2005, background): “Such respresentations of Hamiltonians can arise as encodings of computational problems, such as simulations of quantum walks [6, 7, 8, 9, 10] or adiabatic quantum computations [11].”
Quantum Walk Based Search Algorithms (2008, background): “The potential of discrete time quantum walks with respect to searching problems was ﬁrst pointed out by Shenvi, Kempe, and Whaley [34] who designed a quantum walk based simulation of Grover search.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”
Twisted photons: new quantum perspectives in high dimensions (2017, background): “It has been demonstrated that QW allows for dynamic simulation of complex quantum systems, for the implementation of quantum search algorithms [88] and even universal quantum computation [89].”
Quantum technology for military applications (2021, methodology): “The other approach to searching can be based on the quantum random walk mechanism [44], which offers similar speedup as Grover’s algorithm.”
Quantum walk algorithm for element distinctness (2003, background): “[30] have constructed a counterpart of Grover’s search [23] based on quan tum walk on hypercube.”
Coins make quantum walks faster (2004, methodology): “Hypercube: For instance we can derive the performance of the random walk search algorithm on the hypercube, given in [ SKW03 ] without having to guess the form of the eigenvalues | ±!0i . [SKW03] showed that the random walk search algorithm after time T = �2 √ N gives a probability”
Quantum walks: a comprehensive review (2012, methodology): “(45) which were later used in [409] for the design of a search algorithm based on a discrete quantum walk.”
Exploring topological phases with quantum walks (2010, background): “[3] Shenvi, N.”