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:2307.00791 · Journal of Statistical Physics

Proof of Avoidability of the Quantum First-Order Transition in Transverse Magnetization in Quantum Annealing of Finite-Dimensional Spin Glasses

Mizuki Yamaguchi, Naoto Shiraishi, Koji Hukushima

Published Jan 28, 2024• 0 citations
arXivHTMLPDF

Abstract

Abstract It is rigorously shown that an appropriate quantum annealing for any finite-dimensional spin system has no quantum first-order transition in transverse magnetization. This result can be applied to finite-dimensional spin-glass systems, where the ground state search problem is known to be hard to solve. Consequently, it is strongly suggested that the quantum first-order transition in transverse magnetization is not fatal to the difficulty of combinatorial optimization problems in quantum annealing.

DOI
10.1007/s10955-023-03223-2

Related papers

Quantum annealing with antiferromagnetic fluctuations

Yuya Seki, Hidetoshi Nishimori

We introduce antiferromagnetic quantum fluctuations into quantum annealing in addition to the conventional transverse-field term. We apply this method to the infinite-range ferromagnetic p-spin model, for which the conventional quantum annealing has been shown to have difficulties in finding the ground state efficiently due to a first-order transition. We study the phase diagram of this system both analytically and numerically. Using the static approximation, we find that there exists a quantum path to reach the final ground state from the trivial initial state that avoids first-order transitions for intermediate values of p. We also study numerically the energy gap between the ground state and the first excited state and find evidence for intermediate values of p for which the time complexity scales polynomially with the system size at a second-order transition point along the quantum path that avoids first-order transitions. These results suggest that quantum annealing would be able to solve this problem with intermediate values of p efficiently, in contrast to the case with only simple transverse-field fluctuations.

arXiv:1203.2418•Physical Review E•May 10, 2012•134 citations

Quantum annealing with antiferromagnetic transverse interactions for the Hopfield model

Yuya Seki, Hidetoshi Nishimori

We investigate quantum annealing (QA) with antiferromagnetic transverse interactions for the generalized Hopfield model with k -body interactions. The goal is to study the effectiveness of antiferromagnetic interactions, which were shown to help us avoid problematic first-order quantum phase transitions in pure ferromagnetic systems, in random systems. We estimate the efficiency of QA by analyzing phase diagrams for two cases where the number of embedded patterns is finite or extensively large. The phase diagrams of the model with finite patterns show that there exist annealing paths that avoid first-order transitions at least for . The same is true for the extensive case with k = 4 and 5. In contrast, it is impossible to avoid first-order transitions for the case of finite patterns with k = 3 and the case of extensive number of patterns with k = 2 and 3. The spin-glass phase hampers the QA process in the case of k = 2 and extensive patterns. These results indicate that QA with antiferromagnetic transverse interactions is efficient also for certain random spin systems.

arXiv:1410.0450•Journal of Physics A Mathematical and Theoretical•Jul 24, 2015•63 citations

Phase transitions in quantum annealing of an NP-hard problem detected by fidelity susceptibility

Jun Takahashi, Koji Hukushima

Abstract Quantum annealing (QA) for the NP-hard maximum independent set problem with a unique solution is studied using the quantum Monte Carlo method. A fraction of the samples exhibit first-order phase transitions in terms of the spin-glass order parameter q . Moreover, while no singularities could be observed for the sample-averaged , a divergence in the sample-averaged fidelity susceptibility is found. Since all of the first-order transitions of q occur with smaller transverse field strength compared to the divergence point of , it is likely that the phase detected by induces the first-order transitions. This suggests that failures of QA due to exponentially small energy gaps are phenomena within this underlying phase.

Journal of Statistical Mechanics Theory and Experiment•Apr 1, 2019•4 citations

The quantum transition of the two-dimensional Ising spin glass

Massimo Bernaschi, I. González-Adalid Pemartín, Víctor Martín-Mayor +1 more

Abstract Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5–9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11–13.

arXiv:2310.07486•Nature•Jul 10, 2024•35 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

Simple Glass Models and Their Quantum Annealing

Thomas Jörg, Florent Krząkała, Jorge Kurchan B +1 more

We study first-order quantum phase transitions in mean-field spin glasses. We solve the quantum random energy model using elementary methods and show that at the transition the eigenstate suddenly projects onto the unperturbed ground state and that the gap between the lowest states is exponentially small in the system size. We argue that this is a generic feature of all "random first-order" models, which includes benchmarks such as random satisfiability. We introduce a two-time instanton to calculate this gap in general, and discuss the consequences for quantum annealing.

arXiv:0806.4144•Physical Review Letters•Oct 2, 2008•109 citations
Abstract It is rigorously shown that an appropriate quantum annealing for any finite-dimensional spin system has no quantum first-order transition in transverse magnetization. This result can be applied to finite-dimensional spin-glass systems, where the ground state search problem is known to be hard to solve. Consequently, it is strongly suggested that the quantum first-order transition in transverse magnetization is not fatal to the difficulty of combinatorial optimization problems in quantum annealing.
We introduce antiferromagnetic quantum fluctuations into quantum annealing in addition to the conventional transverse-field term. We apply this method to the infinite-range ferromagnetic p-spin model, for which the conventional quantum annealing has been shown to have difficulties in finding the ground state efficiently due to a first-order transition. We study the phase diagram of this system both analytically and numerically. Using the static approximation, we find that there exists a quantum path to reach the final ground state from the trivial initial state that avoids first-order transitions for intermediate values of p. We also study numerically the energy gap between the ground state and the first excited state and find evidence for intermediate values of p for which the time complexity scales polynomially with the system size at a second-order transition point along the quantum path that avoids first-order transitions. These results suggest that quantum annealing would be able to solve this problem with intermediate values of p efficiently, in contrast to the case with only simple transverse-field fluctuations.
We investigate quantum annealing (QA) with antiferromagnetic transverse interactions for the generalized Hopfield model with k -body interactions. The goal is to study the effectiveness of antiferromagnetic interactions, which were shown to help us avoid problematic first-order quantum phase transitions in pure ferromagnetic systems, in random systems. We estimate the efficiency of QA by analyzing phase diagrams for two cases where the number of embedded patterns is finite or extensively large. The phase diagrams of the model with finite patterns show that there exist annealing paths that avoid first-order transitions at least for . The same is true for the extensive case with k = 4 and 5. In contrast, it is impossible to avoid first-order transitions for the case of finite patterns with k = 3 and the case of extensive number of patterns with k = 2 and 3. The spin-glass phase hampers the QA process in the case of k = 2 and extensive patterns. These results indicate that QA with antiferromagnetic transverse interactions is efficient also for certain random spin systems.
Abstract Quantum annealing (QA) for the NP-hard maximum independent set problem with a unique solution is studied using the quantum Monte Carlo method. A fraction of the samples exhibit first-order phase transitions in terms of the spin-glass order parameter q . Moreover, while no singularities could be observed for the sample-averaged , a divergence in the sample-averaged fidelity susceptibility is found. Since all of the first-order transitions of q occur with smaller transverse field strength compared to the divergence point of , it is likely that the phase detected by induces the first-order transitions. This suggests that failures of QA due to exponentially small energy gaps are phenomena within this underlying phase.
Abstract Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5–9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11–13.
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.
We study first-order quantum phase transitions in mean-field spin glasses. We solve the quantum random energy model using elementary methods and show that at the transition the eigenstate suddenly projects onto the unperturbed ground state and that the gap between the lowest states is exponentially small in the system size. We argue that this is a generic feature of all "random first-order" models, which includes benchmarks such as random satisfiability. We introduce a two-time instanton to calculate this gap in general, and discuss the consequences for quantum annealing.