Spatial search and the Dirac equation
arXiv:quant-ph/0405120 · doi:10.1103/PhysRevA.70.042312
Abstract
We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
5 pages, 1 figure
References in corpus (5)
Cited by in corpus (82)
- Universal computation by quantum walk
- Universal quantum computation using the discrete time quantum walk
- On the relationship between continuous- and discrete-time quantum walk
- Quantum algorithms for algebraic problems
- Search via Quantum Walk
- Decoherence in quantum walks - a review
- Faster quantum walk algorithm for the two dimensional spatial search
- Entanglement in coined quantum walks on regular graphs
- Quantum walks on general graphs
- Relativistic quantum walks
- Limit distributions of two-dimensional quantum walks
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Towards High-Fidelity Quantum Computation and Simulation on a Programmable Photonic Integrated Circuit
- Quantum walk approach to search on fractal structures
- Quantum walks can find a marked element on any graph
- Discrete Time Quantum Walk Approach to State Transfer
- The Dirac equation as a quantum walk: higher dimensions, observational convergence
- Quantum Random Walks do not need a Coin Toss
- Quadratic speedup for spatial search by continuous-time quantum walk
- Nonlinear optical Galton board
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Almost uniform sampling via quantum walks
- Quantum Walks, Quantum Gates and Quantum Computers
- Hamiltonian Oracles
- Quantum Walks
- Faster Search by Lackadaisical Quantum Walk
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Spatial search by continuous-time quantum walks on crystal lattices
- On the optimality of spatial search by continuous-time quantum walk
- Decoherence and Quantum Walks: anomalous diffusion and ballistic tails
- Tailoring discrete quantum walk dynamics via extended initial conditions: Towards homogeneous probability distributions
- Quantum search on graphene lattices
- Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
- Efficient quantum circuits for arbitrary sparse unitaries
- Quantum Search with Multiple Walk Steps per Oracle Query
- The Elephant Quantum Walk
- Quantum Walks on Trees with Disorder: Decay, Diffusion, and Localization
- Quantum walks and quantum search on graphene lattices
- On the adiabatic condition and the quantum hitting time of Markov chains
- General framework for quantum search algorithms
- Finding a marked node on any graph by continuous-time quantum walk
- Electric quantum walks in two dimensions
- Quantum walk algorithm for element distinctness
- Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
- Spin systems dynamics and faults detection in threshold networks
- Continuous Time Quantum Walks in finite Dimensions
- Limits on Efficient Computation in the Physical World
- Lackadaisical quantum walk for spatial search
- Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs
- N-dimensional alternate coined quantum walks from a dispersion relation perspective
- Engineering topological states and quantum-inspired information processing using classical circuits
- Discrete-time quantum walks on one-dimensional lattices
- Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up
- Quantum search with interacting Bose-Einstein condensates
- Speed and entropy of an interacting continuous time quantum walk
- The quantum walk search algorithm: Factors affecting efficiency
- Probability distributions for Markov chains based quantum walks
- Generic quantum walk using a coin-embedded shift operator
- Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
- Quantum walk search by Grover search on coin space
- Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
- Search of clustered marked states with lackadaisical quantum walks
- Quantum walk search on a two-dimensional grid with extra edges
- On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
- Quantum Snake Walk on Graphs
- Quantum walk state transfer on a hypercube
- Search by quantum walks on two-dimensional grid without amplitude amplification
- Quantum search on Hanoi network
- Short time behavior of continuous time quantum walks on graphs
- Coherence as resource in scattering quantum walk search on complete graph
- Two-particle coined-quantum walk with long-range interaction
- Interference-induced localization in quantum random walk on clean cyclic graph
- Quantum Algorithms: Database Search and its Variations
- Quantum walks assisted by particle number fluctuations
- Search and state transfer between hubs by quantum walks
- Quantum walk search for exceptional configurations
- Searching via nonlinear quantum walk on the 2D-grid
- Spatial search using the discrete time quantum walk
- Quantum Search of Spatial Regions
- Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
- Quantum Walks, Feynman Propagators and Graph Topology on an IBM Quantum Computer
- A universal adiabatic quantum query algorithm