Lower Bounds on Quantum Annealing Times
arXiv:2210.15687 · doi:10.1103/PhysRevLett.130.140601
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.
accepted to PRL
References in corpus (6)
- Bounds for the adiabatic approximation with applications to quantum computation
- Quantum annealing with antiferromagnetic fluctuations
- Focus on Shortcuts to Adiabaticity
- 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
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