Skip to main content

Spatial search by continuous-time quantum walks on crystal lattices

Abstract

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 łog 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.

Publication Details

Authors
Publication Type
Journal Article
Year of Publication
2014
Journal
Physical Review A
Volume
89
Date Published
05/2014