Spatial search and the Dirac equation

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 √N for $d>2$ and of order √N0.3em0exlog0.3em0exN 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.