01263nas a2200133 4500008004100000245003500041210003500076260001400111490000700125520090700132100002301039700002301062856004401085 2004 eng d00aSpatial search by quantum walk0 aSpatial search by quantum walk c2004/8/230 v703 a 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.
1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0306054v2