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

Physical Review Letters

Soft Annealing: A New Approach to Difficult Computational Problems

Nicolas Sourlas

Published Feb 23, 2005• 8 citations
Publisher

Abstract

I propose a new method to study computationally difficult problems. I consider a new system, larger than the one I want to simulate. The original system is recovered by imposing constraints on the large system. I simulate the large system with the hard constraints replaced by soft constraints. I illustrate the method in the case of a ferromagnetic Ising model and in the case of a three-dimensional spin-glass model. I show that in both models the phases of the soft problem have the same properties as the phases of the original model and that the softened model belongs to the same universality class as the original one. I show that correlation times are much shorter in the larger soft constrained system and that it is computationally advantageous to study it instead of the original system. This method is quite general and can be applied to many other systems.

DOI
10.1103/physrevlett.94.070601

Related papers

Soft Annealing: A New Approach to Difficult Computational Problems

Nicolas Sourlas

I propose a new method to study computationally difficult problems. I consider a new system, larger than the one I want to simulate. The original system is recovered by imposing constraints on the large system. I simulate the large system with the hard constraints replaced by soft constraints. I illustrate the method in the case of the ferromagnetic Ising model and in the case the three dimensional spin-glass model. I show in both the ferromagnetic Ising and the spin-glass model that the phases of the soft problem have the same properties with the phases of the original model and that the softened model belongs to the same universality class as the original one. I show that correlation times are much shorter in the larger soft constrained system and that it is computationally advantageous to study it instead of the original system. This method is quite general and can be applied to other systems.

arXiv:cond-mat/0408082•Progress of Theoretical Physics Supplement•Jan 1, 2005•0 citations

Dual time scales in simulated annealing of a two-dimensional Ising Spin Glass

Na Xu, Shanon J. Rubin, Anders W. Sandvik

Bulletin of the American Physical Society•Mar 16, 2017•1 citation

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

Optimising simulated quantum annealing, simulated annealing and a mean-field algorithm to find ground states of Ising spin glasses

Damian S. Steiger, Troels F. R Onnow, Matthias Troyer

Bulletin of the American Physical Society•Mar 4, 2015•0 citations

Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo +1 more

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

arXiv:1609.06558•Physical review. B./Physical review. B•May 15, 2017•109 citations

Temperature-disorder phase diagram of a three-dimensional gauge-glass model

Vincenzo Alba, Ettore Vicari

We investigate the temperature-disorder ($T$-$\ensuremath{\sigma}$) phase diagram of a three-dimensional gauge glass model, which is a cubic-lattice nearest-neighbor $\mathit{XY}$ model with quenched random phase shifts ${A}_{\mathit{xy}}$ at the bonds. We consider the uncorrelated phase-shift distribution $P({A}_{\mathit{xy}})~\mathrm{exp}[(\mathrm{cos}{A}_{\mathit{xy}})/\ensuremath{\sigma}]$, which has the pure $\mathit{XY}$ model, and the uniform distribution of random phase shifts as extreme cases at $\ensuremath{\sigma}=0$ and $\ensuremath{\sigma}\ensuremath{\rightarrow}\ensuremath{\infty}$, respectively, and which gives rise to equal magnetic and overlap correlation functions when $T=\ensuremath{\sigma}$. Our study is mostly based on numerical Monte Carlo simulations. While the high-temperature phase is always paramagnetic, at low temperatures there is a ferromagnetic phase for weak disorder (small $\ensuremath{\sigma}$) and a glassy phase at large disorder (large $\ensuremath{\sigma}$). These three phases are separated by transition lines with different magnetic and glassy critical behaviors. The disorder induced by the random phase shifts turns out to be irrelevant at the paramagnetic-ferromagnetic transition line, where the critical behavior belongs to the 3D $\mathit{XY}$ universality class of pure systems; disorder gives rise only to very slowly decaying scaling corrections. The glassy critical behavior along the paramagnetic-glassy transition line belongs to the gauge-glass universality class, with a quite large exponent $\ensuremath{\nu}=3.2(4)$. These transition lines meet at a multicritical point M, located at ${T}_{M}={\ensuremath{\sigma}}_{M}=0.7840(2)$. The low-temperature ferromagnetic and glassy phases are separated by a third transition line, from M down to the $T=0$ axis, which is slightly reentrant.

arXiv:1012.2432•Physical Review B•Mar 25, 2011•8 citations
I propose a new method to study computationally difficult problems. I consider a new system, larger than the one I want to simulate. The original system is recovered by imposing constraints on the large system. I simulate the large system with the hard constraints replaced by soft constraints. I illustrate the method in the case of a ferromagnetic Ising model and in the case of a three-dimensional spin-glass model. I show that in both models the phases of the soft problem have the same properties as the phases of the original model and that the softened model belongs to the same universality class as the original one. I show that correlation times are much shorter in the larger soft constrained system and that it is computationally advantageous to study it instead of the original system. This method is quite general and can be applied to many other systems.
I propose a new method to study computationally difficult problems. I consider a new system, larger than the one I want to simulate. The original system is recovered by imposing constraints on the large system. I simulate the large system with the hard constraints replaced by soft constraints. I illustrate the method in the case of the ferromagnetic Ising model and in the case the three dimensional spin-glass model. I show in both the ferromagnetic Ising and the spin-glass model that the phases of the soft problem have the same properties with the phases of the original model and that the softened model belongs to the same universality class as the original one. I show that correlation times are much shorter in the larger soft constrained system and that it is computationally advantageous to study it instead of the original system. This method is quite general and can be applied to other systems.
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.
Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.
We investigate the temperature-disorder (TTT-$\ensuremath{\sigma}$) phase diagram of a three-dimensional gauge glass model, which is a cubic-lattice nearest-neighbor XY\mathit{XY}XY model with quenched random phase shifts Axy{A}_{\mathit{xy}}Axy​ at the bonds. We consider the uncorrelated phase-shift distribution $P({A}_{\mathit{xy}})~\mathrm{exp}[(\mathrm{cos}{A}_{\mathit{xy}})/\ensuremath{\sigma}]$, which has the pure XY\mathit{XY}XY model, and the uniform distribution of random phase shifts as extreme cases at $\ensuremath{\sigma}=0$ and $\ensuremath{\sigma}\ensuremath{\rightarrow}\ensuremath{\infty}$, respectively, and which gives rise to equal magnetic and overlap correlation functions when $T=\ensuremath{\sigma}$. Our study is mostly based on numerical Monte Carlo simulations. While the high-temperature phase is always paramagnetic, at low temperatures there is a ferromagnetic phase for weak disorder (small $\ensuremath{\sigma}$) and a glassy phase at large disorder (large $\ensuremath{\sigma}$). These three phases are separated by transition lines with different magnetic and glassy critical behaviors. The disorder induced by the random phase shifts turns out to be irrelevant at the paramagnetic-ferromagnetic transition line, where the critical behavior belongs to the 3D XY\mathit{XY}XY universality class of pure systems; disorder gives rise only to very slowly decaying scaling corrections. The glassy critical behavior along the paramagnetic-glassy transition line belongs to the gauge-glass universality class, with a quite large exponent $\ensuremath{\nu}=3.2(4)$. These transition lines meet at a multicritical point M, located at ${T}_{M}={\ensuremath{\sigma}}_{M}=0.7840(2)$. The low-temperature ferromagnetic and glassy phases are separated by a third transition line, from M down to the T=0T=0T=0 axis, which is slightly reentrant.