Quantum Walk Search through Potential Barriers
arXiv:1503.06605 · doi:10.1088/1751-8113/49/48/484002
Abstract
An ideal quantum walk transitions from one vertex to another with perfect fidelity, but in physical systems, the particle may be hindered by potential energy barriers. Then the particle has some amplitude of tunneling through the barriers, and some amplitude of staying put. We investigate the algorithmic consequence of such barriers for the quantum walk formulation of Grover's algorithm. We prove that the failure amplitude must scale as for search to retain its quantum runtime; otherwise, it searches in classical time. Thus searching larger "databases" requires increasingly reliable hop operations or error correction. This condition holds for both discrete- and continuous-time quantum walks.
arXiv comment13 pages, 7 figures
References in corpus (14)
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- From quantum cellular automata to quantum lattice gases
- Universal computation by multi-particle quantum walk
- On Arbitrary Phases in Quantum Amplitude Amplification
- Phase matching in quantum searching
- On the absence of homogeneous scalar unitary cellular automata
- Global Symmetry is Unnecessary for Fast Quantum Search
- Quantum algorithms for hidden nonlinear structures
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Quantum Search with Multiple Walk Steps per Oracle Query
- Quantum Walk on the Line through Potential Barriers