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

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)

Simulated Quantum Annealing of the Wishart Planted Ensemble

E. V. Burlakov, M. A. Yarygin

Published May 11, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/weconf69969.2026.11553816

Related papers

Tunneling through high energy barriers in simulated quantum annealing

Elizabeth Crosson, Mingkai Deng

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.

arXiv:1410.8484•Oct 30, 2014•16 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•1 citation

Optimization by quantum annealing: Lessons from hard satisfiability problems

Demian A. Battaglia, Giuseppe E. Santoro, Erio Tosatti

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

arXiv:cond-mat/0502468•Physical Review E•Jun 29, 2005•111 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•2 citations

Hybrid annealing: Coupling a quantum simulator to a classical computer

Tobias Graß, Maciej Lewenstein

Finding the global minimum in a rugged potential landscape is a computationally hard task, often equivalent to relevant optimization problems. Annealing strategies, either classical or quantum, explore the configuration space by evolving the system under the influence of thermal or quantum fluctuations. The thermal annealing dynamics can rapidly freeze the system into a low-energy configuration, and it can be simulated well on a classical computer, but it easily gets stuck in local minima. Quantum annealing, on the other hand, can be guaranteed to find the true ground state and can be implemented in modern quantum simulators; however, quantum adiabatic schemes become prohibitively slow in the presence of quasidegeneracies. Here, we propose a strategy which combines ideas from simulated annealing and quantum annealing. In such a hybrid algorithm, the outcome of a quantum simulator is processed on a classical device. While the quantum simulator explores the configuration space by repeatedly applying quantum fluctuations and performing projective measurements, the classical computer evaluates each configuration and enforces a lowering of the energy. We have simulated this algorithm for small instances of the random energy model, showing that it potentially outperforms both simulated thermal annealing and adiabatic quantum annealing. It becomes most efficient for problems involving many quasidegenerate ground states.

arXiv:1611.09729•Physical Review A•May 3, 2017•12 citations

Distinguishing thermal versus quantum annealing using probability-flux signatures across interaction networks

Yoshiaki Horiike, Yuki Kawaguchi

Simulated annealing provides a heuristic solution to combinatorial optimization problems. The cost function of a problem is mapped onto the energy function of a physical many-body system, and, by using thermal or quantum fluctuations, the system explores the state space to find the ground state, which corresponds to the optimal solution of the problem. Studies have highlighted both the similarities and differences between thermal and quantum fluctuations. Nevertheless, fundamental understanding of thermal and quantum annealing remains incomplete, making it unclear how quantum annealing outperforms thermal annealing in which problem instances. Here, we investigate the many-body dynamics of thermal and quantum annealing by examining all possible interaction networks of $\pm J$ Ising spin systems up to seven spins. Our comprehensive investigation reveals that differences between thermal and quantum annealing emerge for particular interaction networks, indicating that the structure of the energy landscape distinguishes the two dynamics. We identify the microscopic origin of these differences through probability fluxes in state space, finding that the two dynamics are broadly similar, but that quantum tunnelling produces qualitative differences. Our results provide insight into how thermal and quantum fluctuations navigate a system toward the ground state in simulated annealing, and are experimentally verifiable in atomic, molecular, and optical systems. Furthermore, these insights may improve mappings of optimization problems to Ising spin systems, yielding more accurate solutions in faster simulated annealing and thus benefiting real-world applications in industry. Our comprehensive survey of interaction networks and visualization of probability flux can help to understand, predict, and control quantum advantage in quantum annealing.

cond-mat.stat-mechCross-listedarXiv:2511.16457•Nov 21, 2025•1 citation
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.
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.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
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.
Finding the global minimum in a rugged potential landscape is a computationally hard task, often equivalent to relevant optimization problems. Annealing strategies, either classical or quantum, explore the configuration space by evolving the system under the influence of thermal or quantum fluctuations. The thermal annealing dynamics can rapidly freeze the system into a low-energy configuration, and it can be simulated well on a classical computer, but it easily gets stuck in local minima. Quantum annealing, on the other hand, can be guaranteed to find the true ground state and can be implemented in modern quantum simulators; however, quantum adiabatic schemes become prohibitively slow in the presence of quasidegeneracies. Here, we propose a strategy which combines ideas from simulated annealing and quantum annealing. In such a hybrid algorithm, the outcome of a quantum simulator is processed on a classical device. While the quantum simulator explores the configuration space by repeatedly applying quantum fluctuations and performing projective measurements, the classical computer evaluates each configuration and enforces a lowering of the energy. We have simulated this algorithm for small instances of the random energy model, showing that it potentially outperforms both simulated thermal annealing and adiabatic quantum annealing. It becomes most efficient for problems involving many quasidegenerate ground states.
Simulated annealing provides a heuristic solution to combinatorial optimization problems. The cost function of a problem is mapped onto the energy function of a physical many-body system, and, by using thermal or quantum fluctuations, the system explores the state space to find the ground state, which corresponds to the optimal solution of the problem. Studies have highlighted both the similarities and differences between thermal and quantum fluctuations. Nevertheless, fundamental understanding of thermal and quantum annealing remains incomplete, making it unclear how quantum annealing outperforms thermal annealing in which problem instances. Here, we investigate the many-body dynamics of thermal and quantum annealing by examining all possible interaction networks of ±J\pm J±J Ising spin systems up to seven spins. Our comprehensive investigation reveals that differences between thermal and quantum annealing emerge for particular interaction networks, indicating that the structure of the energy landscape distinguishes the two dynamics. We identify the microscopic origin of these differences through probability fluxes in state space, finding that the two dynamics are broadly similar, but that quantum tunnelling produces qualitative differences. Our results provide insight into how thermal and quantum fluctuations navigate a system toward the ground state in simulated annealing, and are experimentally verifiable in atomic, molecular, and optical systems. Furthermore, these insights may improve mappings of optimization problems to Ising spin systems, yielding more accurate solutions in faster simulated annealing and thus benefiting real-world applications in industry. Our comprehensive survey of interaction networks and visualization of probability flux can help to understand, predict, and control quantum advantage in quantum annealing.