Key points are not available for this paper at this time.
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. 3em{0ex}poly (log0. 3em{0ex}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 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. 3em{0ex}poly (log0. 3em{0ex}N), and in d<4, the algorithm does not provide substantial speedup.
Childs et al. (Mon,) studied this question.