Lower Bounds on Quantum Annealing Times

Abstract

The adiabatic theorem provides sufficient conditions for the time needed to prepare a target ground state. While it is possible to prepare a target state much faster with more general quantum annealing protocols, rigorous results beyond the adiabatic regime are rare. Here, we provide such a result, deriving lower bounds on the time needed to successfully perform quantum annealing. The bounds are asymptotically saturated by three toy models where fast annealing schedules are known: the Roland and Cerf unstructured search model, the Hamming spike problem, and the ferromagnetic p-spin model. Our bounds demonstrate that these schedules have optimal scaling. Our results also show that rapid annealing requires coherent superpositions of energy eigenstates, singling out quantum coherence as a computational resource.

arXiv commentaccepted to PRL

References in corpus (33)

• Quantifying Coherence
• Quantum Annealing in the Transverse Ising Model
• Quantum Coherence as a Resource
• Adiabatic Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• Quantum Search by Local Adiabatic Evolution
• Shortcuts to adiabaticity by counter-diabatic driving
• Perspectives of quantum annealing: Methods and implementations
• Bounds for the adiabatic approximation with applications to quantum computation
• Trace-distance measure of coherence
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Anderson localization casts clouds over adiabatic quantum optimization
• Coherence depletion in the Grover quantum search algorithm
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• Focus on Shortcuts to Adiabaticity
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• On quantum mean-field models and their quantum annealing
• On the Role of Coherence in Shor's Algorithm
• Counterdiabatic driving in the quantum annealing of the $p$-spin model: a variational approach
• Fast adiabatic evolution by oscillating initial Hamiltonians
• Necessary Condition for the Quantum Adiabatic Approximation
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Genetic optimization of quantum annealing
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Analog Nature of Quantum Adiabatic Unstructured Search
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Necessary Adiabatic Run Times in Quantum Optimization
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• How Quantum is the Speedup in Adiabatic Unstructured Search?

Cited by in corpus (10)

• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Adaptive variational simulation for open quantum systems
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Limits on the Evolutionary Rates of Biological Traits
• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO
• Tighter Lower Bounds on Quantum Annealing Times
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Optimized adiabatic-impulse protocol preserving Kibble-Zurek scaling with attenuated anti-Kibble-Zurek behavior