



01350nas a2200181   4500008004100000245004400041210004400085260001300129490000800142520083200150653002700982653003101009100003201040700002101072700002201093700001601115856003701131       2023                        eng d00aLower Bounds on Quantum Annealing Times0 aLower Bounds on Quantum Annealing Times  c4/5/20230 v1303 a<p>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.</p>10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aGarcía-Pintos, Luis, Pedro1 aBrady, Lucas, T.1 aBringewatt, Jacob1 aLiu, Yi-Kai  uhttps://arxiv.org/abs/2210.15687