2014/03/31 by Andrew M. Childs, Yimin Ge · 1 citation
Computer Science · Physics and Astronomy · #Computer science #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum computer #Quantum mechanics #Quantum walk #Quantum-Dot Cellular Automata #Statistical physics #quant-ph
paper · pdf · doi:10.1103/physreva.89.052337
published as Phys. Rev. A 89, 052337 (2014) · 12 pages, 11 figures
openalex publication_date 2014/05/30 · arxiv created 2014/09/05 · arxiv updated 2014/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 behavior near a Dirac point, we develop algorithms that solve the problem in a time of O(√(N)) for d>2 and O(√(N)\phantom\rule0.16em0exlogN) 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.