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

Analytical solution for ground state estimation by a nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian

Bin Yan, Nikolai A. Sinitsyn

Published Oct 24, 2021• 0 citations
OpenAlex

Abstract

We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian $H_I$ by implementing time evolution with a Hamiltonian $H(t)=H_I+g(t) H_t$. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling $g(t)$ and a specific mixing Hamiltonian $H_t$ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of $H_I$, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time $T$ and uncorrelated from the $H_I$ annealing schedule. This proves the possibility for spin glasses of a faster than $\sim 1/\log^{\beta} T$ energy relaxation.

Related papers

Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian

Bin Yan, Nikolai A. Sinitsyn

Abstract Ising spin Hamiltonians are often used to encode a computational problem in their ground states. Quantum Annealing (QA) computing searches for such a state by implementing a slow time-dependent evolution from an easy-to-prepare initial state to a low energy state of a target Ising Hamiltonian of quantum spins, H I . Here, we point to the existence of an analytical solution for such a problem for an arbitrary H I beyond the adiabatic limit for QA. This solution provides insights into the accuracy of nonadiabatic computations. Our QA protocol in the pseudo-adiabatic regime leads to a monotonic power-law suppression of nonadiabatic excitations with time T of QA, without any signature of a transition to a glass phase, which is usually characterized by a logarithmic energy relaxation. This behavior suggests that the energy relaxation can differ in classical and quantum spin glasses strongly, when it is assisted by external time-dependent fields. In specific cases of H I , the solution also shows a considerable quantum speedup in computations.

arXiv:2110.12354•Nature Communications•Apr 25, 2022•23 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

Necessary adiabatic run times in quantum optimization

Lucas T. Brady, Wim van Dam

Quantum annealing is guaranteed to find the ground state of optimization problems provided it operates in the adiabatic limit. Recent work [S. Muthukrishnan et al., Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an $n$-qubit optimization problem was presented for which a nonadiabatic, or diabatic, annealing algorithm requires only a constant run time, while an adiabatic annealing algorithm requires a run-time polynomial in $n$. Here we show that this nonadiabatic speedup is the direct result of a specific symmetry in the studied problem. In the more general case, no such nonadiabatic speedup occurs and we show why the special case achieves this speedup compared to the general case. We also prove that the adiabatic annealing algorithm has a necessary and sufficient run time that is quadratically better than the standard quantum adiabatic condition suggests. We conclude with an observation about the required precision in timing for the diabatic algorithm.

arXiv:1611.02585•Physical Review A•Mar 30, 2017•18 citations

Quantum Annealing Algorithms for Estimating Ising Partition Functions

Haowei Li, Zhiyuan Yao, Xingze Qiu

Estimating partition functions of Ising spin glasses is a cornerstone of statistical physics and computational science, yet it remains classically challenging due to its #P-hard complexity. While Jarzynski's equality offers a theoretical pathway, its practical application is crippled at low temperatures by rare, divergent statistical fluctuations. Here, we introduce a quantum protocol that overcomes this fundamental limitation by synergizing reverse quantum annealing with optimized nonequilibrium initial distributions. Our method dramatically suppresses the estimator variance, achieving saturation in the low-temperature regime where existing methods fail. Numerical benchmarks on the Sherrington-Kirkpatrick spin glass and the 3-SAT problem demonstrate that our protocol reduces computational scaling exponents by over an order of magnitude (e.g., from ∼8.5 to ∼0.5), despite retaining exponential system-size dependence. Crucially, our protocol circumvents stringent adiabatic constraints, making it feasible for near-term quantum devices like superconducting qubits, trapped ions, and Rydberg atom arrays. This Letter provides a methodological framework for quantum-enhanced estimation in spin glass thermodynamics and beyond by harnessing nonadiabatic quantum dynamics to address a classically difficult problem.

arXiv:2504.21666•Physical Review Letters•Feb 11, 2026•1 citation

Quantum Annealing and Thermalization: Insights from Integrability

Fuxiang Li, Vladimir Chernyak, Nikolai A. Sinitsyn

We solve a model that has basic features that are desired for quantum annealing computations: entanglement in the ground state, controllable annealing speed, ground state energy separated by a gap during the whole evolution, and a programmable computational problem that is encoded by parameters of the Ising part of the spin Hamiltonian. Our solution enables exact nonperturbative characterization of final nonadiabatic excitations, including a scaling of their number with the annealing rate and the system size. We prove that quantum correlations can accelerate computations and, at the end of the annealing protocol, lead to the perfect Gibbs distribution of all microstates.

arXiv:1804.00371•Physical Review Letters•Nov 6, 2018•20 citations

Quantum versus classical annealing of Ising spin glasses

Bettina Heim, Troels F. Rønnow, Sergei V. Isakov +1 more

Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.

arXiv:1411.5693•Science•Mar 12, 2015•218 citations
We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian HIH_IHI​ by implementing time evolution with a Hamiltonian H(t)=HI+g(t)HtH(t)=H_I+g(t) H_tH(t)=HI​+g(t)Ht​. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling g(t)g(t)g(t) and a specific mixing Hamiltonian HtH_tHt​ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of HIH_IHI​, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time TTT and uncorrelated from the HIH_IHI​ annealing schedule. This proves the possibility for spin glasses of a faster than ∼1/log⁡βT\sim 1/\log^{\beta} T∼1/logβT energy relaxation.
Abstract Ising spin Hamiltonians are often used to encode a computational problem in their ground states. Quantum Annealing (QA) computing searches for such a state by implementing a slow time-dependent evolution from an easy-to-prepare initial state to a low energy state of a target Ising Hamiltonian of quantum spins, H I . Here, we point to the existence of an analytical solution for such a problem for an arbitrary H I beyond the adiabatic limit for QA. This solution provides insights into the accuracy of nonadiabatic computations. Our QA protocol in the pseudo-adiabatic regime leads to a monotonic power-law suppression of nonadiabatic excitations with time T of QA, without any signature of a transition to a glass phase, which is usually characterized by a logarithmic energy relaxation. This behavior suggests that the energy relaxation can differ in classical and quantum spin glasses strongly, when it is assisted by external time-dependent fields. In specific cases of H I , the solution also shows a considerable quantum speedup in computations.
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 guaranteed to find the ground state of optimization problems provided it operates in the adiabatic limit. Recent work [S. Muthukrishnan et al., Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an nnn-qubit optimization problem was presented for which a nonadiabatic, or diabatic, annealing algorithm requires only a constant run time, while an adiabatic annealing algorithm requires a run-time polynomial in nnn. Here we show that this nonadiabatic speedup is the direct result of a specific symmetry in the studied problem. In the more general case, no such nonadiabatic speedup occurs and we show why the special case achieves this speedup compared to the general case. We also prove that the adiabatic annealing algorithm has a necessary and sufficient run time that is quadratically better than the standard quantum adiabatic condition suggests. We conclude with an observation about the required precision in timing for the diabatic algorithm.
Estimating partition functions of Ising spin glasses is a cornerstone of statistical physics and computational science, yet it remains classically challenging due to its #P-hard complexity. While Jarzynski's equality offers a theoretical pathway, its practical application is crippled at low temperatures by rare, divergent statistical fluctuations. Here, we introduce a quantum protocol that overcomes this fundamental limitation by synergizing reverse quantum annealing with optimized nonequilibrium initial distributions. Our method dramatically suppresses the estimator variance, achieving saturation in the low-temperature regime where existing methods fail. Numerical benchmarks on the Sherrington-Kirkpatrick spin glass and the 3-SAT problem demonstrate that our protocol reduces computational scaling exponents by over an order of magnitude (e.g., from ∼8.5 to ∼0.5), despite retaining exponential system-size dependence. Crucially, our protocol circumvents stringent adiabatic constraints, making it feasible for near-term quantum devices like superconducting qubits, trapped ions, and Rydberg atom arrays. This Letter provides a methodological framework for quantum-enhanced estimation in spin glass thermodynamics and beyond by harnessing nonadiabatic quantum dynamics to address a classically difficult problem.
We solve a model that has basic features that are desired for quantum annealing computations: entanglement in the ground state, controllable annealing speed, ground state energy separated by a gap during the whole evolution, and a programmable computational problem that is encoded by parameters of the Ising part of the spin Hamiltonian. Our solution enables exact nonperturbative characterization of final nonadiabatic excitations, including a scaling of their number with the annealing rate and the system size. We prove that quantum correlations can accelerate computations and, at the end of the annealing protocol, lead to the perfect Gibbs distribution of all microstates.
Quantum annealers use quantum fluctuations to escape local minima and find low-energy configurations of a physical system. Strong evidence for superiority of quantum annealing (QA) has come from comparing QA implemented through quantum Monte Carlo (QMC) simulations to classical annealing. Motivated by recent experiments, we revisit the question of when quantum speedup may be expected. Although a better scaling is seen for QA in two-dimensional Ising spin glasses, this advantage is due to time discretization artifacts and measurements that are not possible on a physical quantum annealer. Simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care must be taken when using QMC simulations to assess the potential for quantum speedup.