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:1801.05511 · Nature Communications

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

Anurag Mishra, Tameem Albash, Daniel A. Lidar

Published Jul 19, 2018• 48 citations
arXivHTMLPDF

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 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.

DOI
10.1038/s41467-018-05239-9

Related papers

When finite temperature quantum annealing defies expectations based on gap scaling

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 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.

•Jan 17, 2018•1 citation

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 Adiabatic Algorithm and Scaling of Gaps at First-Order Quantum Phase Transitions

Chris R. Laumann, Roderich Moessner, Antonello Scardicchio +1 more

Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.

arXiv:1202.3646•Physical Review Letters•Jul 19, 2012•71 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

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

Computational Bottlenecks of Quantum Annealing

Sergey Knysh

A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) 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 localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. 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.

arXiv:1506.08608•Jun 29, 2015•3 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 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.
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.
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.
Motivated by the quantum adiabatic algorithm (QAA), we consider the scaling of the Hamiltonian gap at quantum first-order transitions, generally expected to be exponentially small in the size of the system. However, we show that a quantum antiferromagnetic Ising chain in a staggered field can exhibit a first-order transition with only an algebraically small gap. In addition, we construct a simple classical translationally invariant one-dimensional Hamiltonian containing nearest-neighbor interactions only, which exhibits an exponential gap at a thermodynamic quantum first-order transition of essentially topological origin. This establishes that (i) the QAA can be successful even across first-order transitions but also that (ii) it can fail on exceedingly simple problems readily solved by inspection, or by classical annealing.
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.
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.
A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of NNN qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log⁡N)O(\log N)O(logN) bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller NNN, 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.