Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Lower Bounds on Quantum Annealing Times

Published

Author(s)

Luis Pedro Garcia-Pintos, Lucas Brady, Jacob Bringewatt, Yi-Kai Liu

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.
Citation
Physical Review Letters
Volume
130

Keywords

Quantum mechanics, adiabatic theorem, quantum annealing

Citation

Garcia-Pintos, L. , Brady, L. , Bringewatt, J. and Liu, Y. (2023), Lower Bounds on Quantum Annealing Times, Physical Review Letters, [online], https://doi.org/10.1103/PhysRevLett.130.140601, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935713 (Accessed March 3, 2024)
Created April 5, 2023, Updated April 7, 2023