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:1410.8484

Tunneling through high energy barriers in simulated quantum annealing

Elizabeth Crosson, Mingkai Deng

Published Oct 30, 2014• 9 citations
arXivHTMLPDF

Abstract

We analyze the performance of simulated quantum annealing (SQA) on an optimization problem for which simulated classical annealing (SA) is provably inefficient because of a high energy barrier. We present evidence that SQA can pass through this barrier to find the global minimum efficiently. This demonstrates the potential for SQA to inherit some of the advantages of quantum annealing (QA), since this problem has been previously shown to be efficiently solvable by quantum adiabatic optimization.

DOI
10.48550/arxiv.1410.8484

Related papers

Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.

arXiv:1601.03030•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•76 citations

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width n^ζ and height n^α for ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.

•Oct 1, 2016•89 citations

Simulated Quantum Annealing is Efficient on the Spike Hamiltonian

Thiago Bergamaschi

In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.

arXiv:2011.15094•Nov 30, 2020•0 citations

Quantum and classical annealing in a continuous space with multiple local minima

Yang Wei Koh, Hidetoshi Nishimori

The protocol of quantum annealing is applied to an optimization problem with a one-dimensional continuous degree of freedom, a variant of the problem proposed by Shinomoto and Kabashima. The energy landscape has a number of local minima, and the classical approach of simulated annealing is predicted to have a logarithmically slow convergence to the global minimum. We show by extensive numerical analyses that quantum annealing yields a power-law convergence, thus an exponential improvement over simulated annealing. The power is larger, and thus the convergence is faster, than a prediction by an existing phenomenological theory for this problem. Performance of simulated annealing is shown to be enhanced by introducing quasiglobal searches across energy barriers, leading to a power-law convergence but with a smaller power than in the quantum case and thus a slower convergence classically even with quasiglobal search processes. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum by a meticulous choice of annealing schedule. This latter result explicitly contrasts the role of tunneling in quantum annealing against the classical counterpart of stochastic optimization by simulated annealing.

arXiv:2203.11417•Physical Review A•Jun 21, 2022•13 citations

When Does Quantum Annealing Outperform Classical Methods? A Gradient Variance Framework

Vishwajeet Ohal, Pierre Boulanger

Quantum annealing has emerged as a promising approach for solving NP-hard optimization problems, leveraging quantum phenomena such as quantum tunneling to navigate complex energy landscapes. However, the extent to which quantum tunneling contributes to performance enhancements compared to classical methods remains unclear. In this work, we present a comprehensive investigation combining experimental analysis, theoretical modeling, and algorithmic development to characterize when and why quantum annealing provides computational advantages. We introduce a novel methodology for generating synthetic Quadratic Unconstrained Binary Optimization (QUBO) problems with controlled gradient variance, enabling systematic investigation of landscape characteristics that favor quantum approaches. Our experimental evaluation encompasses four canonical NP-hard problems: Graph Partitioning, Max Cut, Number Partitioning, and Set Cover. Using D-Wave's Advantage2 quantum annealer with 4,400+ qubits, we compare quantum annealing against classical solvers including simulated annealing, stochastic gradient descent, and commercial optimization software. Our results demonstrate that quantum annealing shows measurable advantages when energy landscapes exhibit high gradient variance ($> 0.3$), suggesting that quantum tunneling effects are most beneficial for rugged optimization landscapes. We provide a theoretical justification for this empirical observation through a WKB-approximation-based model connecting gradient variance to barrier width and tunneling probability. This model achieves $R^2=0.90$ correlation with experimental data and yields quantitative predictions for quantum advantage thresholds.

quant-pharXiv:2602.16875•Feb 20, 2026•0 citations

Simulated Quantum Annealing of the Wishart Planted Ensemble

Evgenii V. Burlakov, M. A. Yarygin

This work investigates the performance of simulated quantum annealing on the Wishart Planted Ensemble, a tunable spin-glass model with a known global minimum and a non-monotonic hardness profile. A direct comparison between classical simulated annealing and simulated quantum annealing is carried out in the hard regime. We show that on energy landscapes where simulated annealing fails to reach the planted state, simulated quantum annealing - at optimal inverse temperatures - consistently attains significantly lower energies, approaching the global optimum. These results demonstrate the advantage of emulating quantum tunneling over purely thermal fluctuations in landscapes characterized by high but narrow energy barriers.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•May 11, 2026•0 citations
We analyze the performance of simulated quantum annealing (SQA) on an optimization problem for which simulated classical annealing (SA) is provably inefficient because of a high energy barrier. We present evidence that SQA can pass through this barrier to find the global minimum efficiently. This demonstrates the potential for SQA to inherit some of the advantages of quantum annealing (QA), since this problem has been previously shown to be efficiently solvable by quantum adiabatic optimization.
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width n^ζ and height n^α for ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.
In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.
The protocol of quantum annealing is applied to an optimization problem with a one-dimensional continuous degree of freedom, a variant of the problem proposed by Shinomoto and Kabashima. The energy landscape has a number of local minima, and the classical approach of simulated annealing is predicted to have a logarithmically slow convergence to the global minimum. We show by extensive numerical analyses that quantum annealing yields a power-law convergence, thus an exponential improvement over simulated annealing. The power is larger, and thus the convergence is faster, than a prediction by an existing phenomenological theory for this problem. Performance of simulated annealing is shown to be enhanced by introducing quasiglobal searches across energy barriers, leading to a power-law convergence but with a smaller power than in the quantum case and thus a slower convergence classically even with quasiglobal search processes. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum by a meticulous choice of annealing schedule. This latter result explicitly contrasts the role of tunneling in quantum annealing against the classical counterpart of stochastic optimization by simulated annealing.
Quantum annealing has emerged as a promising approach for solving NP-hard optimization problems, leveraging quantum phenomena such as quantum tunneling to navigate complex energy landscapes. However, the extent to which quantum tunneling contributes to performance enhancements compared to classical methods remains unclear. In this work, we present a comprehensive investigation combining experimental analysis, theoretical modeling, and algorithmic development to characterize when and why quantum annealing provides computational advantages. We introduce a novel methodology for generating synthetic Quadratic Unconstrained Binary Optimization (QUBO) problems with controlled gradient variance, enabling systematic investigation of landscape characteristics that favor quantum approaches. Our experimental evaluation encompasses four canonical NP-hard problems: Graph Partitioning, Max Cut, Number Partitioning, and Set Cover. Using D-Wave's Advantage2 quantum annealer with 4,400+ qubits, we compare quantum annealing against classical solvers including simulated annealing, stochastic gradient descent, and commercial optimization software. Our results demonstrate that quantum annealing shows measurable advantages when energy landscapes exhibit high gradient variance (>0.3> 0.3>0.3), suggesting that quantum tunneling effects are most beneficial for rugged optimization landscapes. We provide a theoretical justification for this empirical observation through a WKB-approximation-based model connecting gradient variance to barrier width and tunneling probability. This model achieves R2=0.90R^2=0.90R2=0.90 correlation with experimental data and yields quantitative predictions for quantum advantage thresholds.
This work investigates the performance of simulated quantum annealing on the Wishart Planted Ensemble, a tunable spin-glass model with a known global minimum and a non-monotonic hardness profile. A direct comparison between classical simulated annealing and simulated quantum annealing is carried out in the hard regime. We show that on energy landscapes where simulated annealing fails to reach the planted state, simulated quantum annealing - at optimal inverse temperatures - consistently attains significantly lower energies, approaching the global optimum. These results demonstrate the advantage of emulating quantum tunneling over purely thermal fluctuations in landscapes characterized by high but narrow energy barriers.