Quantum walk search through potential barriers

DOI10.1088/1751-8113/49/48/484002MaRDI QIDQ3178738zbMATH OpenOpenAlexFDO

Authors Thomas G. Wong

Publication date 20 December 2016

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.06605

zbMATH Keywords

Grover's algorithmpotential barrierquantum searchquantum tunnelingquantum walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Searching and sorting (68P10) Quantum computation (81P68) Quantum stochastic calculus (81S25)

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 $O(1/sqrtN)$ for search to retain its quantum $O(sqrtN)$ runtime; otherwise, it searches in classical $O(N)$ time. Thus searching larger "databases" requires increasingly reliable hop operations or error correction. This condition holds for both discrete- and continuous-time quantum walks.

Recommendations

• Quantum walk search with time-reversal symmetry breaking
• Quantum walk on the line through potential barriers
• Gate imperfection in the quantum random-walk search algorithm
• Quantum Walk Based Search Algorithms
• Quantum walks and search algorithms

Cited in

(10)

• Equivalence of Szegedy's and coined quantum walks
• Fast quantum search of multiple vertices based on electric circuits
• Quantum walk on the line through potential barriers
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Search via quantum walks with intermediate measurements
• Search via Quantum Walk
• Robust quantum spatial search
• Quantum walk search with time-reversal symmetry breaking
• The quantum walk search algorithm: factors affecting efficiency
• Robustness of quantum walk search with neighbors measurement

This page was built for publication: Quantum walk search through potential barriers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178738)