The quantum walk search algorithm: Factors affecting efficiency
arXiv:1110.4366 · doi:10.1017/S0960129518000051
Abstract
We numerically study the quantum walk search algorithm of Shenvi, Kempe and Whaley [PRA \textbf{67} 052307] and the factors which affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. Here, we consider the effects of interpolating between dimensions, connectivity of the dataset, and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that, as well as the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. In addition, we also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.
arXiv comment37 pages, 34 figures - submitted to Mathematical Structures in Computer Science
References in corpus (33)
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Spatial search by quantum walk
- Grover's quantum searching algorithm is optimal
- Universal quantum computation using the discrete time quantum walk
- Controlling discrete quantum walks: coins and intitial states
- Quantum walks in higher dimensions
- Decoherence in quantum walks - a review
- Weak limits for quantum random walks
- Decoherence can be useful in quantum walks
- Faster quantum walk algorithm for the two dimensional spatial search
- Localization of Two-Dimensional Quantum Walks
- Spatial search and the Dirac equation
- Hitting time for quantum walks on the hypercube
- Localization and its consequences for quantum walk algorithms and quantum communication
- Quantum walks on general graphs
- Optimized quantum random-walk search algorithms
- Quantum walks with infinite hitting times
- Quantum walks on quotient graphs
- Quantum searches on highly symmetric graphs
- Universal quantum computation by discontinuous quantum walk
- Coined quantum walks on percolation graphs
- Quantum search algorithms on a regular lattice
- Spatial search in a honeycomb network
- Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
- Quantum search algorithms on the hypercube
- Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
- Convergence of continuous-time quantum walks on the line
- Mixing Times in Quantum Walks on Two-Dimensional Grids
Cited by in corpus (6)
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
- Optimizing the spatial spread of a quantum walk
- Decoherence on Staggered Quantum Walks
- Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
- Two-particle Hadamard walk on dynamically percolated line and circle