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.