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

When finite temperature quantum annealing defies expectations based on gap scaling

Anurag Mishra, Tameem Albash, Daniel A. Lidar

Published Jan 17, 2018• 1 citation
OpenAlex

Abstract

Closed-system quantum annealing is expected to sometimes fail spectacularly in solving simple problems for which the gap becomes exponentially small in the problem size. Much less is known about whether this gap scaling also impedes open-system quantum annealing. Here we study the performance of a quantum annealing processor in solving the problem of a ferromagnetic chain with sectors of alternating coupling strength. Despite being trivial classically, this is a problem for which the transverse field Ising model is known to exhibit an exponentially decreasing gap in the sector size, suggesting an exponentially decreasing success probability in the sector size if the annealing time is kept fixed. We find that the behavior of the quantum annealing processor departs significantly from this expectation, with the success probability rising and recovering for sufficiently large sector sizes. Rather than correlating with the size of the minimum energy gap, the success probability exhibits a strong correlation with the number of thermally accessible excited states at the critical point. We demonstrate that this behavior is consistent with a quantum open-system description of the process and is unrelated to thermal relaxation. Our results indicate that even when the minimum gap is several orders of magnitude smaller than the processor temperature, the system properties at the critical point still determine the performance of the quantum annealer.

Related papers

Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability

Anurag Mishra, Tameem Albash, Daniel A. Lidar

Closed-system quantum annealing is expected to sometimes fail spectacularly in solving simple problems for which the gap becomes exponentially small in the problem size. Much less is known about whether this gap scaling also impedes open-system quantum annealing. Here, we study the performance of a quantum annealing processor in solving such a problem: a ferromagnetic chain with sectors of alternating coupling strength that is classically trivial but exhibits an exponentially decreasing gap in the sector size. The gap is several orders of magnitude smaller than the device temperature. Contrary to the closed-system expectation, the success probability rises for sufficiently large sector sizes. The success probability is strongly correlated with the number of thermally accessible excited states at the critical point. We demonstrate that this behavior is consistent with a quantum open-system description that is unrelated to thermal relaxation, and is instead dominated by the system's properties at the critical point.

arXiv:1801.05511•Nature Communications•Jul 19, 2018•48 citations

Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy

Hiroshi Hayasaka, Takashi Imoto, Yuichiro Matsuzaki +1 more

Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where $L$ is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic $p$-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.

arXiv:2212.09995•Physical Review A•Aug 26, 2024•4 citations

Quantum-annealing correction at finite temperature: Ferromagnetic p -spin models

Shunji Matsuura, Hidetoshi Nishimori, Walter Vinci +2 more

The performance of open-system quantum annealing is adversely affected by thermal excitations out of the ground state. While the presence of energy gaps between the ground and excited states suppresses such excitations, error correction techniques are required to ensure full scalability of quantum annealing. Quantum annealing correction (QAC) is a method that aims to improve the performance of quantum annealers when control over only the problem (final) Hamiltonian is possible, along with decoding. Building on our earlier work [S. Matsuura et al., Phys. Rev. Lett. 116, 220501 (2016)], we study QAC using analytical tools of statistical physics by considering the effects of temperature and a transverse field on the penalty qubits in the ferromagnetic $p$-body infinite-range transverse-field Ising model. We analyze the effect of QAC on second ($p=2$) and first ($p\ensuremath{\ge}3$) order phase transitions, and construct the phase diagram as a function of temperature and penalty strength. Our analysis reveals that for sufficiently low temperatures and in the absence of a transverse field on the penalty qubit, QAC breaks up a single, large free-energy barrier into multiple smaller ones. We find theoretical evidence for an optimal penalty strength in the case of a transverse field on the penalty qubit, a feature observed in QAC experiments. Our results provide further compelling evidence that QAC provides an advantage over unencoded quantum annealing.

arXiv:1610.09535•Physical Review A•Feb 7, 2017•41 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

Zero-temperature quantum annealing bottlenecks in the spin-glass phase

Sergey Knysh

A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.

Nature Communications•Aug 5, 2016•79 citations

Quantum annealing for hard 2-satisfiability problems: Distribution and scaling of minimum energy gap and success probability

Vrinda Mehta, Fengping Jin, Hans A. De Raedt +1 more

In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.

arXiv:2202.00118•Physical Review A•Jun 3, 2022•11 citations
Closed-system quantum annealing is expected to sometimes fail spectacularly in solving simple problems for which the gap becomes exponentially small in the problem size. Much less is known about whether this gap scaling also impedes open-system quantum annealing. Here we study the performance of a quantum annealing processor in solving the problem of a ferromagnetic chain with sectors of alternating coupling strength. Despite being trivial classically, this is a problem for which the transverse field Ising model is known to exhibit an exponentially decreasing gap in the sector size, suggesting an exponentially decreasing success probability in the sector size if the annealing time is kept fixed. We find that the behavior of the quantum annealing processor departs significantly from this expectation, with the success probability rising and recovering for sufficiently large sector sizes. Rather than correlating with the size of the minimum energy gap, the success probability exhibits a strong correlation with the number of thermally accessible excited states at the critical point. We demonstrate that this behavior is consistent with a quantum open-system description of the process and is unrelated to thermal relaxation. Our results indicate that even when the minimum gap is several orders of magnitude smaller than the processor temperature, the system properties at the critical point still determine the performance of the quantum annealer.
Closed-system quantum annealing is expected to sometimes fail spectacularly in solving simple problems for which the gap becomes exponentially small in the problem size. Much less is known about whether this gap scaling also impedes open-system quantum annealing. Here, we study the performance of a quantum annealing processor in solving such a problem: a ferromagnetic chain with sectors of alternating coupling strength that is classically trivial but exhibits an exponentially decreasing gap in the sector size. The gap is several orders of magnitude smaller than the device temperature. Contrary to the closed-system expectation, the success probability rises for sufficiently large sector sizes. The success probability is strongly correlated with the number of thermally accessible excited states at the critical point. We demonstrate that this behavior is consistent with a quantum open-system description that is unrelated to thermal relaxation, and is instead dominated by the system's properties at the critical point.
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where LLL is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic ppp-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
The performance of open-system quantum annealing is adversely affected by thermal excitations out of the ground state. While the presence of energy gaps between the ground and excited states suppresses such excitations, error correction techniques are required to ensure full scalability of quantum annealing. Quantum annealing correction (QAC) is a method that aims to improve the performance of quantum annealers when control over only the problem (final) Hamiltonian is possible, along with decoding. Building on our earlier work [S. Matsuura et al., Phys. Rev. Lett. 116, 220501 (2016)], we study QAC using analytical tools of statistical physics by considering the effects of temperature and a transverse field on the penalty qubits in the ferromagnetic ppp-body infinite-range transverse-field Ising model. We analyze the effect of QAC on second (p=2p=2p=2) and first ($p\ensuremath{\ge}3$) order phase transitions, and construct the phase diagram as a function of temperature and penalty strength. Our analysis reveals that for sufficiently low temperatures and in the absence of a transverse field on the penalty qubit, QAC breaks up a single, large free-energy barrier into multiple smaller ones. We find theoretical evidence for an optimal penalty strength in the case of a transverse field on the penalty qubit, a feature observed in QAC experiments. Our results provide further compelling evidence that QAC provides an advantage over unencoded quantum annealing.
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.
A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.
In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiability (2-SAT) problems, consisting of problems of up to 18 variables, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types: ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We find that although the scaling of the runtime is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in the case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Finally, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.