Lower Bounds on Quantum Annealing Times

Area of Science:

• Quantum Computing
• Quantum Annealing
• Theoretical Physics

Background:

• The adiabatic theorem offers guidelines for preparing ground states in quantum systems.
• Faster quantum annealing protocols exist but lack rigorous theoretical bounds outside the adiabatic regime.

Purpose of the Study:

• To derive rigorous lower bounds on the time required for successful quantum annealing.
• To demonstrate the optimality of known fast annealing schedules.
• To identify the role of quantum coherence in rapid annealing.

Main Methods:

• Derivation of analytical lower bounds for quantum annealing time.
• Analysis of specific models including the Roland and Cerf unstructured search, Hamming spike, and p-spin models.
• Asymptotic analysis of annealing schedules.

Main Results:

• Established rigorous lower bounds on quantum annealing time.
• Demonstrated that the derived bounds are asymptotically saturated by known fast annealing schedules, proving their optimal scaling.
• Showcased that rapid annealing necessitates coherent superpositions of energy eigenstates.

Conclusions:

• The derived bounds provide a theoretical foundation for understanding the limits of quantum annealing speed.
• Fast quantum annealing schedules for specific problems exhibit optimal time scaling.
• Quantum coherence is identified as an essential computational resource for achieving rapid quantum annealing.