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}\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.

12 pages, 11 figures

References in corpus (5)

• Spatial search by quantum walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Quantum search on graphene lattices
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2

Cited by in corpus (30)

• Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Quadratic speedup for spatial search by continuous-time quantum walk
• On the optimality of spatial search by continuous-time quantum walk
• Quantum transport in d-dimensional lattices
• Microwave Experiments Simulating Quantum Search and Directed Transport in Artificial Graphene
• Quantum walks and quantum search on graphene lattices
• One-Dimensional Coinless Quantum Walks
• Finding a marked node on any graph by continuous-time quantum walk
• Quantum spatial search in two-dimensional waveguide arrays
• Continuous Time Quantum Walks in finite Dimensions
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Analog quantum algorithms for the mixing of Markov chains
• Quantum-classical distance as a tool to design optimal chiral quantum walk
• Feedback-assisted quantum search by continuous-time quantum walks
• Continuous-time quantum walks on planar lattices and the role of the magnetic field
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Percolation assisted excitation transport in discrete-time quantum walks
• Boundary-induced coherence in the staggered quantum walk on different topologies
• Quantum search in many-body interacting system with long-range interaction
• Efficient quantum walk on the grid with multiple marked elements
• Nonlinear three-state quantum walks
• Suitable bases for quantum walks with Wigner coins
• Optimal spatial searches with long-range tunneling
• Universal dynamical scaling laws in three-state quantum walks
• Persistence of unvisited sites in quantum walks on a line
• Searching via nonlinear quantum walk on the 2D-grid
• Realizing Topological Quantum Walks on NISQ Digital Quantum Computer
• Optimal quantum spatial search with one-dimensional long-range interactions
• Optimal detection of quantum states via projective measurements