Lower Bounds on Quantum Annealing Times

作     者：Luis Pedro García-Pintos Lucas T. Brady Jacob Bringewatt Yi-Kai Liu 

作者机构：Joint Center for Quantum Information and Computer Science University of Maryland College Park Maryland 20742 USA Joint Quantum Institute University of Maryland College Park Maryland 20742 USA Theoretical Division (T4) Los Alamos National Laboratory Los Alamos New Mexico 87545 USA Quantum Artificial Intelligence Laboratory NASA Ames Research Center Moffett Field California 94035 USA KBR 601 Jefferson Street Houston Texas 77002 USA Applied and Computational Mathematics Division National Institute of Standards and Technology Gaithersburg Maryland 20899 USA 

出 版 物：《Physical Review Letters》 (Phys Rev Lett)

年 卷 期：2023年第130卷第14期

页      面：140601-140601页

核心收录：

学科分类：07[理学] 0702[理学-物理学] 

基　　金：National Science Foundation, NSF Air Force Office of Scientific Research, AFOSR Army Research Laboratory, ARL Heising-Simons Foundation, HSF U.S. Department of Energy, USDOE Office of Science, SC Defense Advanced Research Projects Agency, DARPA, (PHY-1748958) Defense Advanced Research Projects Agency, DARPA Simons Foundation, SF, (216179) Simons Foundation, SF Quantum Leap Challenge Institutes, (OMA-2120757) FAR-QC, (80ARC020D0010) Advanced Scientific Computing Research, ASCR, (DE-SC0020312) Advanced Scientific Computing Research, ASCR National Aeronautics and Space Administration, NASA, (IAA 8839) National Aeronautics and Space Administration, NASA National Nuclear Security Administration, NNSA, (DEAC52-06NA25396) National Nuclear Security Administration, NNSA DOE ASCR Quantum Testbed Pathfinder program, (DE-SC0019040) 

主　　题：Adiabatic quantum optimization Quantum algorithms Quantum computation 

摘      要：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.