Spatial search by quantum walk

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 √N for $d>2$, and in time of order √N0.3em0expoly(log0.3em0exN) 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 √N speedup can also be achieved on the hypercube. We show that full √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 √N0.3em0expoly(log0.3em0exN), and in $d<4$, the algorithm does not provide substantial speedup.