Journal
PHYSICAL REVIEW A
Volume 70, Issue 2, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.70.022314
Keywords
-
Categories
Ask authors/readers for more resources
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 rootN for d>2, and in time of order rootN 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 rootN speedup can also be achieved on the hypercube. We show that full rootN 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 rootN poly(log N), and in d<4, the algorithm does not provide substantial speedup.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available