Quantum walk search through potential barriers

DOI10.1088/1751-8113/49/48/484002zbMATH Open1354.81010arXiv1503.06605OpenAlexW3104257085MaRDI QIDQ3178738FDOQ3178738

Authors: Thomas G. Wong 

Publication date: 20 December 2016

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

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.

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

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

zbMATH Keywords

quantum tunnelingquantum walkGrover's algorithmquantum searchpotential barrier

Mathematics Subject Classification ID

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

Cited In (10)

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

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)