Analog Nature of Quantum Adiabatic Unstructured Search

Abstract

The quantum adiabatic unstructured search algorithm is one of only a handful of quantum adiabatic optimization algorithms to exhibit provable speedups over their classical counterparts. With no fault tolerance theorems to guarantee the resilience of such algorithms against errors, understanding the impact of imperfections on their performance is of both scientific and practical significance. We study the robustness of the algorithm against various types of imperfections: limited control over the interpolating schedule, Hamiltonian misspecification, and interactions with a thermal environment. We find that the unstructured search algorithm's quadratic speedup is generally not robust to the presence of any one of the above non-idealities, and in some cases we find that it imposes unrealistic conditions on how the strength of these noise sources must scale to maintain the quadratic speedup.

7 pages, 3 figures. v2. Updated to published version

References in corpus (14)

• Spatial search by quantum walk
• Bounds for the adiabatic approximation with applications to quantum computation
• Thermal and Residual Excited-State Population in a 3D Transmon Qubit
• How Powerful is Adiabatic Quantum Computation?
• Decoherence in adiabatic quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Noise resistance of adiabatic quantum computation using random matrix theory
• Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
• Efficient discrete-time simulations of continuous-time quantum query algorithms

Cited by in corpus (7)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Lower Bounds on Quantum Annealing Times
• Disorder-assisted graph coloring on quantum annealers
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Assessing the performance of quantum annealing with nonlinear driving