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