Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.14779 · SciPost Physics

Tighter lower bounds on quantum annealing times

Luis Pedro García-Pintos, Mrunmay Sahasrabudhe, Christian Arenz

Published May 16, 2025• 4 citations
arXivHTMLPDF

Abstract

We derive lower bounds on the time needed for a quantum annealer to prepare the ground state of a target Hamiltonian. These bounds do not depend on the annealing schedule and can take the local structure of the Hamiltonian into account. Consequently, the bounds are computable without knowledge of the annealer’s dynamics and, in certain cases, scale with the size of the system. We discuss spin systems where the bounds are polynomially tighter than existing bounds, qualitatively capturing the scaling of the exact annealing times as a function of the number of spins.

DOI
10.21468/scipostphys.18.5.159

Related papers

Lower Bounds on Quantum Annealing Times

Luis Pedro García-Pintos, Lucas T. Brady, Jacob Bringewatt +1 more

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.

arXiv:2210.15687•Physical Review Letters•Apr 5, 2023•17 citations

Trajectory-independent speed limits for controlled open quantum systems

James B. Larsen, Tameem Albash, Alicia B. Magann +1 more

Existing quantum speed limits for controlled open quantum systems depend on the specified trajectory. For example, lower bounds on quantum annealing times in the presence of dissipation depend explicitly on the chosen annealing schedule. Recently, schedule-independent speed limits have been derived for annealing in the closed quantum system setting (SciPost Phys. 18, 159 (2025)). In this work, we generalize these results to open quantum systems, deriving schedule-independent lower bounds for quantum annealing times in systems described by a Lindblad master equation. We analyze the interplay between coherent control and dissipation in single- and two-qubit examples, demonstrating that the derived lower bounds capture key scaling behavior with respect to the strength of the dissipator. Finally, we apply the bound to thermal state preparation and show that the bound matches the expected asymptotic behavior for an Ising model in the high temperature limit.

quant-pharXiv:2603.13090•Physical Review A•Mar 16, 2026•0 citations

Reaching states below the threshold energy in spin glasses via quantum annealing

Christopher L. Baldwin

Although quantum annealing is usually considered as a method for locating the ground states of difficult spin-glass and optimization problems, its use in approximate optimization -- finding low- but not zero-energy states in a reasonably short amount of time -- is no less important. Here we investigate the behavior of quantum annealing at approximate optimization in the canonical mean-field spin-glass models, the spherical $p$-spin models, and find that it performs surprisingly well. Whereas it had long been assumed that infinite-range spin glasses have a unique ``threshold'' energy at which all quench and annealing dynamics become trapped until exponential timescales, recent work has shown that two-stage quenches can in fact reach states below the naive threshold in more generic situations. We demonstrate that quantum annealing is also capable of exploiting this effect to locate sub-threshold states in $O(1)$ time. Not only can it attain energies as far below the threshold as classical annealing algorithms, but it can do so significantly faster: for an annealing schedule taking time $τ$, the residual energy under quantum annealing decays as $τ^{-α}$ with an exponent up to twice as large as that of simulated annealing in the cases considered. Importantly, by deriving and numerically solving closed integro-differential equations that hold in the thermodynamic limit, our results are free from finite-size effects and hold for annealing times that are unambiguously independent of system size.

quant-pharXiv:2603.23602•Mar 26, 2026•0 citations

Limits of Short-Time Quantum Annealing

Ali Hamed Moosavian, Seyed Sajad Kahani, Salman Beigi

Quantum annealing is a general purpose optimization algorithm that is based on the quantum adiabatic theorem. Quantum annealing involves an evolving Hamiltonian that is local. Thus, we expect that short-time quantum annealing algorithms to be inherently local and limited as well. In this paper, we validate this intuition by proving some limitations of short-time quantum annealing algorithms. We show that the distribution of the measurement output of short-time (at most logarithmic) quantum annealing computations are \emph{concentrated} and satisfy an \emph{isoperimetric inequality}. To showcase explicit applications, we also study the \textsc{MaxCut} problem and conclude that quantum annealing needs at least a run-time that scales logarithmically in the problem size to beat classical algorithms. To establish our results, we also prove a Lieb-Robinson bound that works for time-dependent Hamiltonians which might be of independent interest.

•Apr 26, 2021•1 citation

A quantum annealing protocol to solve the nuclear shell model

Emanuele Costa, Axel Pérez-Obiol, J. Menéndez +3 more

The nuclear shell model accurately describes the structure and dynamics of atomic nuclei. However, the exponential scaling of the basis size with the number of degrees of freedom hampers a direct numerical solution for heavy nuclei. In this work, we present a quantum annealing protocol to obtain nuclear ground states. We propose a tailored driver Hamiltonian that preserves a large gap and validate our approach in a dozen nuclei with basis sizes up to 10^5 10 5 using classical simulations of the annealing evolution. We explore the relation between the spectral gap and the total time of the annealing protocol, assessing its accuracy by comparing the fidelity and energy relative error to classical benchmarks. While the nuclear Hamiltonian is non-local and thus challenging to implement in current setups, the estimated computational cost of our annealing protocol on quantum circuits is polynomial in the single-particle basis size, paving the way to study heavier nuclei.

arXiv:2411.06954•SciPost Physics•Aug 29, 2025•7 citations

Quantum resources in non-stoquastic quantum annealing

Chiara Capecci, Sebastian Nagies, Naga Dileep Varikuti +1 more

Quantum annealing promises to solve combinatorial optimization problems by preparing the ground state of a target Hamiltonian. Standard annealing protocols are, however, stoquastic and can thus be simulated by sign-problem-free quantum Monte-Carlo methods. To obtain a true quantum advantage, it has been proposed to use non-stoquastic catalyst Hamiltonians. Active only at intermediate stages of the protocol, these can, for certain problems, convert first-order into second-order quantum phase transitions and thus permit an exponential speedup over the stoquastic protocol. At the same time, the non-stoquastic catalyst renders quantum Monte-Carlo methods inefficient. It remains, however, an open question how other classical computation methods are affected by the non-stoquastic terms. We address this question by computing quantum resources -- entanglement entropy and stabilizer Rényi entropy -- whose presence makes classical computations based on tensor networks and stabilizer-tableau methods exponentially hard. We compare these with the spectral gap along the annealing path for two paradigmatic benchmark models, the fully connected $p$-spin model and a geometrically local Ising model. While the exact behavior shows a subtle dependency on the underlying model and the annealing path, our numerics suggest consistently that the scaling of entanglement and non-stabilizerness is at least maintained in the deeply non-stoquastic regime and in some cases even significantly enhanced. Our results thus suggest that improvements of quantum performance in non-stoquastic annealing coincide with significant presence of quantum computational resources.

quant-pharXiv:2606.09995•Jun 10, 2026•0 citations
We derive lower bounds on the time needed for a quantum annealer to prepare the ground state of a target Hamiltonian. These bounds do not depend on the annealing schedule and can take the local structure of the Hamiltonian into account. Consequently, the bounds are computable without knowledge of the annealer’s dynamics and, in certain cases, scale with the size of the system. We discuss spin systems where the bounds are polynomially tighter than existing bounds, qualitatively capturing the scaling of the exact annealing times as a function of the number of spins.
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.
Existing quantum speed limits for controlled open quantum systems depend on the specified trajectory. For example, lower bounds on quantum annealing times in the presence of dissipation depend explicitly on the chosen annealing schedule. Recently, schedule-independent speed limits have been derived for annealing in the closed quantum system setting (SciPost Phys. 18, 159 (2025)). In this work, we generalize these results to open quantum systems, deriving schedule-independent lower bounds for quantum annealing times in systems described by a Lindblad master equation. We analyze the interplay between coherent control and dissipation in single- and two-qubit examples, demonstrating that the derived lower bounds capture key scaling behavior with respect to the strength of the dissipator. Finally, we apply the bound to thermal state preparation and show that the bound matches the expected asymptotic behavior for an Ising model in the high temperature limit.
Although quantum annealing is usually considered as a method for locating the ground states of difficult spin-glass and optimization problems, its use in approximate optimization -- finding low- but not zero-energy states in a reasonably short amount of time -- is no less important. Here we investigate the behavior of quantum annealing at approximate optimization in the canonical mean-field spin-glass models, the spherical ppp-spin models, and find that it performs surprisingly well. Whereas it had long been assumed that infinite-range spin glasses have a unique ``threshold'' energy at which all quench and annealing dynamics become trapped until exponential timescales, recent work has shown that two-stage quenches can in fact reach states below the naive threshold in more generic situations. We demonstrate that quantum annealing is also capable of exploiting this effect to locate sub-threshold states in O(1)O(1)O(1) time. Not only can it attain energies as far below the threshold as classical annealing algorithms, but it can do so significantly faster: for an annealing schedule taking time τττ, the residual energy under quantum annealing decays as τ−ατ^{-α}τ−α with an exponent up to twice as large as that of simulated annealing in the cases considered. Importantly, by deriving and numerically solving closed integro-differential equations that hold in the thermodynamic limit, our results are free from finite-size effects and hold for annealing times that are unambiguously independent of system size.
Quantum annealing is a general purpose optimization algorithm that is based on the quantum adiabatic theorem. Quantum annealing involves an evolving Hamiltonian that is local. Thus, we expect that short-time quantum annealing algorithms to be inherently local and limited as well. In this paper, we validate this intuition by proving some limitations of short-time quantum annealing algorithms. We show that the distribution of the measurement output of short-time (at most logarithmic) quantum annealing computations are \emph{concentrated} and satisfy an \emph{isoperimetric inequality}. To showcase explicit applications, we also study the \textsc{MaxCut} problem and conclude that quantum annealing needs at least a run-time that scales logarithmically in the problem size to beat classical algorithms. To establish our results, we also prove a Lieb-Robinson bound that works for time-dependent Hamiltonians which might be of independent interest.
The nuclear shell model accurately describes the structure and dynamics of atomic nuclei. However, the exponential scaling of the basis size with the number of degrees of freedom hampers a direct numerical solution for heavy nuclei. In this work, we present a quantum annealing protocol to obtain nuclear ground states. We propose a tailored driver Hamiltonian that preserves a large gap and validate our approach in a dozen nuclei with basis sizes up to 10^5 10 5 using classical simulations of the annealing evolution. We explore the relation between the spectral gap and the total time of the annealing protocol, assessing its accuracy by comparing the fidelity and energy relative error to classical benchmarks. While the nuclear Hamiltonian is non-local and thus challenging to implement in current setups, the estimated computational cost of our annealing protocol on quantum circuits is polynomial in the single-particle basis size, paving the way to study heavier nuclei.
Quantum annealing promises to solve combinatorial optimization problems by preparing the ground state of a target Hamiltonian. Standard annealing protocols are, however, stoquastic and can thus be simulated by sign-problem-free quantum Monte-Carlo methods. To obtain a true quantum advantage, it has been proposed to use non-stoquastic catalyst Hamiltonians. Active only at intermediate stages of the protocol, these can, for certain problems, convert first-order into second-order quantum phase transitions and thus permit an exponential speedup over the stoquastic protocol. At the same time, the non-stoquastic catalyst renders quantum Monte-Carlo methods inefficient. It remains, however, an open question how other classical computation methods are affected by the non-stoquastic terms. We address this question by computing quantum resources -- entanglement entropy and stabilizer Rényi entropy -- whose presence makes classical computations based on tensor networks and stabilizer-tableau methods exponentially hard. We compare these with the spectral gap along the annealing path for two paradigmatic benchmark models, the fully connected ppp-spin model and a geometrically local Ising model. While the exact behavior shows a subtle dependency on the underlying model and the annealing path, our numerics suggest consistently that the scaling of entanglement and non-stabilizerness is at least maintained in the deeply non-stoquastic regime and in some cases even significantly enhanced. Our results thus suggest that improvements of quantum performance in non-stoquastic annealing coincide with significant presence of quantum computational resources.