Quantum random-walk search algorithm
Top Cited Papers
- 23 May 2003
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 67 (5), 052307
- https://doi.org/10.1103/physreva.67.052307
Abstract
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 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.
Keywords
This publication has 6 references indexed in Scilit:
- An Example of the Difference Between Quantum and Classical Random WalksQuantum Information Processing, 2002
- Quantum Simulations of Classical Random Walks and Undirected Graph ConnectivityJournal of Computer and System Sciences, 2001
- Quantum computation and decision treesPhysical Review A, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- Quantum random walksPhysical Review A, 1993