Spatial search by quantum walk
Top Cited Papers
- 23 August 2004
- journal article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 70 (2)
- https://doi.org/10.1103/physreva.70.022314
Abstract
Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order sqrt(N) for d>2, and in time of order sqrt(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous time quantum walk on a graph. The case of the complete graph gives the continuous time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that sqrt(N) speedup can also be achieved on the hypercube. We show that full sqrt(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order sqrt(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup.Comment: v2: 12 pages, 4 figures; published version, with improved arguments for the cases where the algorithm failKeywords
Other Versions
This publication has 12 references indexed in Scilit:
- Quantum random-walk search algorithmPhysical Review A, 2003
- Quantum search by measurementPhysical Review A, 2002
- An Example of the Difference Between Quantum and Classical Random WalksQuantum Information Processing, 2002
- Quantum computation and decision treesPhysical Review A, 1998
- Analog analogue of a digital quantum computationPhysical 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
- On the absence of homogeneous scalar unitary cellular automataPhysics Letters A, 1996
- Random Walks in Multidimensional Spaces, Especially on Periodic LatticesJournal of the Society for Industrial and Applied Mathematics, 1956
- THREE TRIPLE INTEGRALSThe Quarterly Journal of Mathematics, 1939