Accuracy vs run time in adiabatic quantum search

Abstract

Adiabatic quantum algorithms are characterized by their run time and accuracy. The relation between the two is essential for quantifying adiabatic algorithmic performance, yet is often poorly understood. We study the dynamics of a continuous time, adiabatic quantum search algorithm, and find rigorous results relating the accuracy and the run time. Proceeding with estimates, we show that under fairly general circumstances the adiabatic algorithmic error exhibits a behavior with two discernible regimes: the error decreases exponentially for short times, then decreases polynomially for longer times. We show that the well known quadratic speedup over classical search is associated only with the exponential error regime. We illustrate the results through examples of evolution paths derived by minimization of the adiabatic error. We also discuss specific strategies for controlling the adiabatic error and run time.

20 pages, 4 figures

References in corpus (13)

• Bounds for the adiabatic approximation with applications to quantum computation
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Adiabatic approximation in open quantum systems
• Quantum Adiabatic Brachistochrone
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Towards Fault Tolerant Adiabatic Quantum Computation
• A Magnetic Resonance Realization of Decoherence-Free Quantum Computation
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Adiabatic Markovian Dynamics
• Adiabatic quantum search with atoms in a cavity driven by lasers
• Adiabatic preparation without Quantum Phase Transitions
• The adiabatic theorem in the presence of noise
• Adiabatic Rotation, Quantum Search and Preparation of Superposition States