%0 Journal Article
%J Physical Review A
%D 2014
%T Spatial search by continuous-time quantum walks on crystal lattices
%A Andrew M. Childs
%A Yimin Ge
%X We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behaviour near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt N)$ for $d>2$ and $O(\sqrt N \log N)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.
%B Physical Review A
%V 89
%8 2014/5/30
%G eng
%U http://arxiv.org/abs/1403.2676v2
%N 5
%! Phys. Rev. A
%R 10.1103/PhysRevA.89.052337