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 (39)

• Quantum Mechanics helps in searching for a needle in a haystack
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Tight bounds on quantum searching
• Grover's quantum searching algorithm is optimal
• Quantum Search by Local Adiabatic Evolution
• Quantum computers can search rapidly by using almost any transformation
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Robustness of adiabatic quantum computation
• Quantum limits to dynamical evolution
• Bounds for the adiabatic approximation with applications to quantum computation
• The fundamental limit on the rate of quantum dynamics: the unified bound is tight
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Adiabatic Quantum Computation in Open Systems
• A different kind of quantum search
• Adiabatic approximation in open quantum systems
• Inconsistency in the application of the adiabatic theorem
• Consistency of the Adiabatic Theorem
• Quantum Adiabatic Brachistochrone
• Quantitative conditions do not guarantee the validity of the adiabatic approximation
• Error correcting codes for adiabatic quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Towards Fault Tolerant Adiabatic Quantum Computation
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Thermally assisted adiabatic quantum computation
• A Magnetic Resonance Realization of Decoherence-Free Quantum Computation
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• General error estimate for adiabatic quantum computing
• Necessary Condition for the Quantum Adiabatic Approximation
• Adiabatic quantum computation and quantum phase transitions
• Adiabatic Markovian Dynamics
• Adiabatic quantum search with atoms in a cavity driven by lasers
• Adiabatic preparation without Quantum Phase Transitions
• Scalable quantum search using trapped ions
• The adiabatic theorem in the presence of noise
• Adiabatic Rotation, Quantum Search and Preparation of Superposition States

Cited by in corpus (50)

• Adiabatic Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• Decoherence in adiabatic quantum computation
• Adiabatic tracking of quantum many-body dynamics
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum adiabatic machine learning
• Adiabatic quantum algorithm for search engine ranking
• Adiabaticity in open quantum systems
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Speeding up critical system dynamics through optimized evolution
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Improved Error-Scaling for Adiabatic Quantum State Transfer
• Reverse quantum annealing of the $p$-spin model with relaxation
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Improved Error Bounds for the Adiabatic Approximation
• Accelerating adiabatic protocols for entangling two qubits in circuit QED
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
• Optimal Control for Closed and Open System Quantum Optimization
• Fixed-Point Adiabatic Quantum Search
• Accelerated adiabatic quantum gates: optimizing speed versus robustness
• Adiabatic evolution under quantum control
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Error Reduction in Quantum Annealing using Boundary Cancellation: Only the End Matters
• Effects of decoherence on diabatic errors in Majorana braiding
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Randomized gap and amplitude estimation
• The three phases of quantum annealing: fast, slow, and very slow
• Feedback-controlled adiabatic quantum computation
• Bang-bang shortcut to adiabaticity in trapped ion quantum simulators
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Customized quantum annealing schedules
• Optimizing Quantum Adiabatic Algorithm
• Non-Adiabatic Quantum Dynamics of Grover's Adiabatic Search Algorithm
• Quantum battery supercharging via counter-diabatic dynamics
• Shortcuts to thermodynamic quasistaticity
• Failure of the geometric approach prediction of excess work scaling for open and isolated quantum systems
• On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
• Hard instance learning for quantum adiabatic prime factorization
• Virtual mitigation of coherent non-adiabatic transitions by echo verification
• Quantum adiabatic theorem for unbounded Hamiltonians with a cutoff and its application to superconducting circuits
• Demonstration of error-suppressed quantum annealing via boundary cancellation
• Quantum eigenstate broadcasting assisted by a coherent link
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Assessing the performance of quantum annealing with nonlinear driving
• Quasi-adiabatic Grover search via the WKB approximation
• Counterdiabatic driving for random-gap Landau-Zener transitions
• Resilience-Runtime Tradeoff Relations for Quantum Algorithms
• Hierarchical Fusion Method for Scalable Quantum Eigenstate Preparation