Quantum search algorithms on a regular lattice
arXiv:1005.3676 · doi:10.1103/PhysRevA.82.012326
Abstract
Quantum algorithms for searching one or more marked items on a d-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level-splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behaviour for the search time and the localisation probability in the limit of large lattice size including the leading order coefficients. For d=2 and d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.
References in corpus (9)
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Realization of a quantum walk with one and two trapped ions
- Faster quantum walk algorithm for the two dimensional spatial search
- A random walk approach to quantum algorithms
- Optimized quantum random-walk search algorithms
- Quantum search algorithms on the hypercube
Cited by in corpus (14)
- Directional correlations in quantum walks with two particles
- Quantum search on graphene lattices
- Quantum walks and quantum search on graphene lattices
- Photonic quantum walks with four-dimensional coins
- Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
- Generic Quantum Walks with Memory
- One dimensional lazy quantum walks and occupancy rate
- Driven Discrete Time Quantum Walks
- The quantum walk search algorithm: Factors affecting efficiency
- Spatial Search Algorithms on Hanoi Networks
- Optimizing the walk coin in the quantum random walk search algorithm through machine learning
- Quantum walks on two kinds of two-dimensional models
- Quantum Search Algorithms on Hierarchical Networks
- Search and state transfer between hubs by quantum walks