%0 Journal Article
%J Physical Review A
%D 2004
%T Spatial search and the Dirac equation
%A Andrew M. Childs
%A Jeffrey Goldstone
%X We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
%B Physical Review A
%V 70
%8 2004/10/19
%G eng
%U http://arxiv.org/abs/quant-ph/0405120v1
%N 4
%! Phys. Rev. A
%R 10.1103/PhysRevA.70.042312