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

A STUDY OF QUANTUM ANNEALING DEVICES FROM A CLASSICAL PERSPECTIVE

Andrew J. Ochoa

Published Dec 7, 2017• 1 citation
OpenAlex

Abstract

Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.

Related papers

Applications of Spin Glasses across Disciplines: From Complex Systems to Quantum Computing and Algorithm Development

Zheng Zhu

The main subjects of this dissertation are spin glass applications in other disciplines and spin glass algorithms. Spin glasses are magnetic systems with disorder and frustration, and the essential physics of spin glasses lies not in the details of their microscopic interactions but rather in the competition between quenched ferromagnetic and antiferromagnetic interactions. Concepts that arose in the study of spin glasses have led to applications in areas as diverse as computer science, biology, and finance, as well as a variety of others.\n\nIn the first part of this dissertation I study the equilibrium and non-equilibrium properties of Boolean decision problems with competing interactions on scale-free networks in an external bias (a magnetic field). First, I perform finite-temperature Monte Carlo simulations in a field to test the robustness of the spin-glass phase and I show that the system has a spin-glass phase in a field, i.e., it exhibits a de Almeida–Thouless line. Then I study avalanche distributions when the system is driven by a field at zero temperature to test whether the system displays self-organized criticality. The numerical results suggest that avalanches (damage) can spread across the entire system with nonzero probability when the decay exponent of the interaction degree is less than or equal to 2, i.e., that Boolean decision problems on scale-free networks with competing interactions can be fragile when the system is not in thermal equilibrium.\n\nIn the second part of this dissertation I discuss the best-case performance of quantum annealers on native spin-glass benchmarks, i.e., how chaos can affect success probabilities. We perform classical parallel-tempering Monte Carlo simulations of the archetypal benchmark problem, an Ising spin glass, on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, I study the best-case resilience, or the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We compute the upper-bound success probabilities for different instance classes based on these simple error models, and I present strategies for developing robust and hard benchmark instances.\n\nIn the third part of this dissertation I present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by several orders of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits (improved thermalization and achievement of more equiprobable sampling of ground states) of the isoenergetic cluster moves in two and three space dimensions, as well as in the nonplanar Chimera topology found in the D-Wave quantum annealing machine.\n\nFinally, I study the thermodynamic properties of the two-dimensional Edwards-Anderson Ising spin-glass model on a square lattice using the tensor renormalization group method based on a higher-order singular-value decomposition. Our estimates of the partition function without a high precision data type lead to negative values at very low temperatures, thus illustrating that the method can not be applied to frustrated magnetic systems.

•Aug 5, 2015•0 citations

Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities

Zheng Zhu, Andrew J. Ochoa, Stefan Schnabel +2 more

Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here we present results from classical parallel-tempering Monte Carlo simulations combined with isoenergetic cluster moves of the archetypal benchmark problem---an Ising spin glass---on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We restrict this study to the exact ground state, however, the approach can be trivially extended to the inclusion of excited states if the success metric is relaxed. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other (black box) computing paradigm affected by noise.

arXiv:1505.02278•Physical Review A•Jan 11, 2016•77 citations

Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension

Zheng Zhu, Andrew J. Ochoa, Helmut G. Katzgraber

Spin systems with frustration and disorder are notoriously difficult to study, both analytically and numerically. While the simulation of ferromagnetic statistical mechanical models benefits greatly from cluster algorithms, these accelerated dynamics methods remain elusive for generic spin-glass-like systems. Here, we present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by at least one order of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits of the isoenergetic cluster moves in two and three space dimensions, as well as the nonplanar chimera topology found in the D-Wave Inc. quantum annealing machine.

arXiv:1501.05630•Physical Review Letters•Aug 14, 2015•120 citations

Comparison between a quantum annealer and a classical approximation algorithm for computing the ground state of an Ising spin glass

Ran Yacoby, Nathan Schaar, Leon Kellerhals +3 more

Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.

Physical review. E•Mar 28, 2022•11 citations

Quantum-Guided Cluster Algorithms for Combinatorial Optimization

Peter Eder, Aron Kerschbaumer, Jernej Rudi Finžgar +5 more

Finding the ground state of Ising spin glasses is notoriously difficult due to disorder and frustration. Often, this challenge is framed as a combinatorial optimization problem, for which a common strategy employs simulated annealing, a Monte Carlo (MC)-based algorithm that updates spins one at a time. Yet, these localized updates can cause the system to become trapped in local minima. Cluster algorithms (CAs) were developed to address this limitation and have demonstrated considerable success in studying ferromagnetic systems; however, they tend to encounter percolation issues when applied to generic spin glasses. In this work, we introduce a novel CA designed to tackle these challenges by leveraging precomputed two-point correlations, aiming solve combinatorial optimization problems in the form of Max-Cut more efficiently. In our approach, clusters are formed probabilistically based on these correlations. Various classical and quantum algorithms can be employed to generate correlations that embody information about the energy landscape of the problem. By utilizing this information, the algorithm aims to identify groups of spins whose simultaneous flipping induces large transitions in configuration space with high acceptance probability - even at low energy levels - thereby escaping local minima more effectively. Notably, clusters generated using correlations from the Quantum Approximate Optimization Algorithm exhibit high acceptance rates at low temperatures. These acceptance rates often increase with circuit depth, accelerating the algorithm and enabling more efficient exploration of the solution space.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Neural and Tensor Networks in the Study of Quantum Annealing Processors

Tomasz Śmierzchalski

Quantum annealing targets low-energy solutions of Ising/QUBO problems, but reliable assessment requires more than best-energy comparisons. This dissertation develops a benchmarking framework for D-Wave quantum annealers that combines strong classical baselines, sampling and diversity metrics, and thermodynamic cost. Its first contribution, SpinGlassPEPS$.$jl, is a topology-aware tensor-network heuristic for optimization and sampling on Pegasus/Zephyr-like graphs. It maps Ising instances to local Potts clusters, represents the partition function with PEPS, and performs branch-and-bound search in probability space. Benchmarks show that it is a physically interpretable reference solver, though approximate contractions limit its competitiveness on the largest instances. The second contribution treats quantum annealers as effective thermal machines, relating success probability and solution quality to dissipation, entropy production, and effective temperature. Carefully placed pauses can improve performance while reducing thermodynamic cost, although longitudinal fields may become harmful in paused schedules. The thesis also introduces reinforcement-learning post-processing to improve returned samples and exact small-system simulations to probe annealing dynamics. Overall, it argues for quantum-annealing benchmarks that jointly measure algorithmic performance and physical expenditure.

quant-pharXiv:2604.26534•Apr 30, 2026•0 citations
Spin glasses are experiencing a revival due to applications in quantum information\ntheory. In particular, they are the archetypal native benchmark problem for quantum annealing\nmachines. Furthermore, they find applications in fields as diverse as satisfiability,\nneural networks, and general combinatorial optimization problems. As such, developing\nand improving algorithms and methods to study these computationally complex systems\nis of paramount importance to many disciplines. This body of work attempts to attack\nthe problem of solving combinatorial optimization problems by simulating spin glasses\nfrom three sides: classical algorithm development, suggestions for quantum annealing\ndevice design, and improving measurements in realistic physical systems with inherent\nnoise. I begin with the introduction of a cluster algorithm based on Houdayer’s cluster algorithm\nfor two-dimensional Ising spin-glasses that is applicable to any space dimension\nand speeds up thermalization by several orders of magnitude at low temperatures where\nprevious algorithms have difficulty. I show improvement for the D-Wave chimera topology\nand the three-dimensional cubic lattice that increases with the size of the problem.\nOne consequence of adding cluster moves is that for problems with degenerate solutions,\nground-state sampling is improved. I demonstrate an ergodic algorithm to sample ground\nstates through the use of simple Monte Carlo with parallel tempering and cluster moves.\nIn addition, I present a non-ergodic algorithm to generate new solutions from a bank of\nknown solutions. I compare these results against results from quantum annealing utilizing\nthe D-Wave Inc. quantum annealing device. Finally, I present an algorithm for improving\nthe recovery of ground-state solutions from problems with noise by using thermal fluctuations\nto infer the correct solution at the Nishimori temperature. While this method has been\ndemonstrated analytically and numerically for trivial ferromagnetic and Gaussian distributions, a useful metric for more complex Gaussian distributions with added Gaussian noise\nis unavailable. We show improved recovery of numerical solutions on the chimera graph\nwith a ferromagnetic distribution and added Gaussian noise. Next, I direct my focus to the\ndesign of future generations of quantum annealers. The first design is the two-dimensional\nsquare-lattice bimodal spin glass with next-nearest ferrromagnetic interactions proposed\nby Lemke and Campbell claimed to exhibit a finite-temperature spin-glass state for a particular\nrelative strength of the next-nearest to nearest neighbor interactions. Our results\nfrom finite-temperature simulations show the system is in a paramagnetic state in the thermodynamic\nlimit, thus not useful for quantum annealing device designs that would benefit\nfrom a spin-glass phase transition. The second design is the diluted next-nearest neighbor\nIsing spin-glass with Gaussian interactions in an attempt to improve the estimation\nof critical parameter with smaller system sizes by implementing averaging of observables\nover different graph dilutions. To date, this model has shown no improvement. Finally,\nI make suggestions for the choice of distributions of interactions that are robust to noise\nand present a method for using previously unaccessible continuous distributions. I begin\nwith showing the best-case performance of quantum annealing devices. I show results for\nthe resilience, the probability that the ground-state solution has changed due to inherent\nanalog noise in the device, and present strategies for developing robust instance classes.\nThe analog noise is also detrimental to interactions chosen from continuous distributions.\nUsing Gaussian quadratures, I present a method for discretizing continuous distributions\nto reduce noise effects. Simulations on the D-Wave show that the average residual of\nthe ground-state energy with the true ground-state energy is calculated and shown to be\nsmaller in the case of the discrete distribution.
The main subjects of this dissertation are spin glass applications in other disciplines and spin glass algorithms. Spin glasses are magnetic systems with disorder and frustration, and the essential physics of spin glasses lies not in the details of their microscopic interactions but rather in the competition between quenched ferromagnetic and antiferromagnetic interactions. Concepts that arose in the study of spin glasses have led to applications in areas as diverse as computer science, biology, and finance, as well as a variety of others.\n\nIn the first part of this dissertation I study the equilibrium and non-equilibrium properties of Boolean decision problems with competing interactions on scale-free networks in an external bias (a magnetic field). First, I perform finite-temperature Monte Carlo simulations in a field to test the robustness of the spin-glass phase and I show that the system has a spin-glass phase in a field, i.e., it exhibits a de Almeida–Thouless line. Then I study avalanche distributions when the system is driven by a field at zero temperature to test whether the system displays self-organized criticality. The numerical results suggest that avalanches (damage) can spread across the entire system with nonzero probability when the decay exponent of the interaction degree is less than or equal to 2, i.e., that Boolean decision problems on scale-free networks with competing interactions can be fragile when the system is not in thermal equilibrium.\n\nIn the second part of this dissertation I discuss the best-case performance of quantum annealers on native spin-glass benchmarks, i.e., how chaos can affect success probabilities. We perform classical parallel-tempering Monte Carlo simulations of the archetypal benchmark problem, an Ising spin glass, on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, I study the best-case resilience, or the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We compute the upper-bound success probabilities for different instance classes based on these simple error models, and I present strategies for developing robust and hard benchmark instances.\n\nIn the third part of this dissertation I present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by several orders of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits (improved thermalization and achievement of more equiprobable sampling of ground states) of the isoenergetic cluster moves in two and three space dimensions, as well as in the nonplanar Chimera topology found in the D-Wave quantum annealing machine.\n\nFinally, I study the thermodynamic properties of the two-dimensional Edwards-Anderson Ising spin-glass model on a square lattice using the tensor renormalization group method based on a higher-order singular-value decomposition. Our estimates of the partition function without a high precision data type lead to negative values at very low temperatures, thus illustrating that the method can not be applied to frustrated magnetic systems.
Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here we present results from classical parallel-tempering Monte Carlo simulations combined with isoenergetic cluster moves of the archetypal benchmark problem---an Ising spin glass---on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We restrict this study to the exact ground state, however, the approach can be trivially extended to the inclusion of excited states if the success metric is relaxed. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other (black box) computing paradigm affected by noise.
Spin systems with frustration and disorder are notoriously difficult to study, both analytically and numerically. While the simulation of ferromagnetic statistical mechanical models benefits greatly from cluster algorithms, these accelerated dynamics methods remain elusive for generic spin-glass-like systems. Here, we present a cluster algorithm for Ising spin glasses that works in any space dimension and speeds up thermalization by at least one order of magnitude at temperatures where thermalization is typically difficult. Our isoenergetic cluster moves are based on the Houdayer cluster algorithm for two-dimensional spin glasses and lead to a speedup over conventional state-of-the-art methods that increases with the system size. We illustrate the benefits of the isoenergetic cluster moves in two and three space dimensions, as well as the nonplanar chimera topology found in the D-Wave Inc. quantum annealing machine.
Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.
Finding the ground state of Ising spin glasses is notoriously difficult due to disorder and frustration. Often, this challenge is framed as a combinatorial optimization problem, for which a common strategy employs simulated annealing, a Monte Carlo (MC)-based algorithm that updates spins one at a time. Yet, these localized updates can cause the system to become trapped in local minima. Cluster algorithms (CAs) were developed to address this limitation and have demonstrated considerable success in studying ferromagnetic systems; however, they tend to encounter percolation issues when applied to generic spin glasses. In this work, we introduce a novel CA designed to tackle these challenges by leveraging precomputed two-point correlations, aiming solve combinatorial optimization problems in the form of Max-Cut more efficiently. In our approach, clusters are formed probabilistically based on these correlations. Various classical and quantum algorithms can be employed to generate correlations that embody information about the energy landscape of the problem. By utilizing this information, the algorithm aims to identify groups of spins whose simultaneous flipping induces large transitions in configuration space with high acceptance probability - even at low energy levels - thereby escaping local minima more effectively. Notably, clusters generated using correlations from the Quantum Approximate Optimization Algorithm exhibit high acceptance rates at low temperatures. These acceptance rates often increase with circuit depth, accelerating the algorithm and enabling more efficient exploration of the solution space.
Quantum annealing targets low-energy solutions of Ising/QUBO problems, but reliable assessment requires more than best-energy comparisons. This dissertation develops a benchmarking framework for D-Wave quantum annealers that combines strong classical baselines, sampling and diversity metrics, and thermodynamic cost. Its first contribution, SpinGlassPEPS...jl, is a topology-aware tensor-network heuristic for optimization and sampling on Pegasus/Zephyr-like graphs. It maps Ising instances to local Potts clusters, represents the partition function with PEPS, and performs branch-and-bound search in probability space. Benchmarks show that it is a physically interpretable reference solver, though approximate contractions limit its competitiveness on the largest instances. The second contribution treats quantum annealers as effective thermal machines, relating success probability and solution quality to dissipation, entropy production, and effective temperature. Carefully placed pauses can improve performance while reducing thermodynamic cost, although longitudinal fields may become harmful in paused schedules. The thesis also introduces reinforcement-learning post-processing to improve returned samples and exact small-system simulations to probe annealing dynamics. Overall, it argues for quantum-annealing benchmarks that jointly measure algorithmic performance and physical expenditure.