01146nas a2200133 4500008004100000245007200041210006900113260001400182490000700196520073500203100002300938700001400961856003700975 2014 eng d00aSpatial search by continuous-time quantum walks on crystal lattices0 aSpatial search by continuoustime quantum walks on crystal lattic c2014/5/300 v893 a 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.
1 aChilds, Andrew, M.1 aGe, Yimin uhttp://arxiv.org/abs/1403.2676v2