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:1102.3305 · Physical Review E

Inference algorithm for finite-dimensional spin glasses: Belief propagation on the dual lattice

Alejandro Lage-Castellanos, Roberto Mulet, Federico Ricci‐Tersenghi, Tommaso Rizzo

Published Oct 24, 2011• 12 citations
arXivHTMLPDF

Abstract

Starting from a cluster variational method, and inspired by the correctness of the paramagnetic ansatz [at high temperatures in general, and at any temperature in the two-dimensional (2D) Edwards-Anderson (EA) model] we propose a message-passing algorithm--the dual algorithm--to estimate the marginal probabilities of spin glasses on finite-dimensional lattices. We use the EA models in 2D and 3D as benchmarks. The dual algorithm improves the Bethe approximation, and we show that in a wide range of temperatures (compared to the Bethe critical temperature) our algorithm compares very well with Monte Carlo simulations, with the double-loop algorithm, and with exact calculation of the ground state of 2D systems with bimodal and Gaussian interactions. Moreover, it is usually 100 times faster than other provably convergent methods, as the double-loop algorithm. In 2D and 3D the quality of the inference deteriorates only where the correlation length becomes very large, i.e., at low temperatures in 2D and close to the critical temperature in 3D.

DOI
10.1103/physreve.84.046706

Related papers

Characterizing and improving generalized belief propagation algorithms on the 2D Edwards–Anderson model

Eduardo Domínguez, Alejandro Lage-Castellanos, Roberto Mulet +2 more

We study the performance of different message passing algorithms in the two dimensional Edwards Anderson model. We show that the standard Belief Propagation (BP) algorithm converges only at high temperature to a paramagnetic solution. Then, we test a Generalized Belief Propagation (GBP) algorithm, derived from a Cluster Variational Method (CVM) at the plaquette level. We compare its performance with BP and with other algorithms derived under the same approximation: Double Loop (DL) and a two-ways message passing algorithm (HAK). The plaquette-CVM approximation improves BP in at least three ways: the quality of the paramagnetic solution at high temperatures, a better estimate (lower) for the critical temperature, and the fact that the GBP message passing algorithm converges also to non paramagnetic solutions. The lack of convergence of the standard GBP message passing algorithm at low temperatures seems to be related to the implementation details and not to the appearance of long range order. In fact, we prove that a gauge invariance of the constrained CVM free energy can be exploited to derive a new message passing algorithm which converges at even lower temperatures. In all its region of convergence this new algorithm is faster than HAK and DL by some orders of magnitude.

arXiv:1110.1259•Journal of Statistical Mechanics Theory and Experiment•Dec 12, 2011•16 citations

Replica cluster variational method: the replica symmetric solution for the 2D random bond Ising model

Alejandro Lage-Castellanos, Roberto Mulet, Federico Ricci‐Tersenghi +1 more

We present and solve the replica symmetric equations in the context of the replica cluster variational method for the 2D random bond Ising model (including the 2D Edwards–Anderson spin-glass model). First, we solve a linearized version of these equations to obtain the phase diagrams of the model on the square and triangular lattices. In both cases, the spin-glass transition temperatures and the multicritical point estimations improve largely over the Bethe predictions. Moreover, we show that this phase diagram is consistent with the behavior of inference algorithms on single instances of the problem. Finally, we present a method to consistently find approximate solutions to the equations in the glassy phase. The method is applied to the triangular lattice down to T = 0, also in the presence of an external field.

arXiv:1204.0439•Journal of Physics A Mathematical and Theoretical•Mar 13, 2013•20 citations

Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs

David Poulin, Ersen Bilgin

Belief propagation---a powerful heuristic method to solve inference problems involving a large number of random variables---was recently generalized to quantum theory. Like its classical counterpart, this algorithm is exact on trees when the appropriate independence conditions are met and is expected to provide reliable approximations when operated on loopy graphs. In this paper, we benchmark the performances of loopy quantum belief propagation (QBP) in the context of finite-temperature quantum many-body physics. Our results indicate that QBP provides reliable estimates of the high-temperature correlation function when the typical loop size in the graph is large. As such, it is suitable, e.g., for the study of quantum spin glasses on Bethe lattices and the decoding of sparse quantum error correction codes.

arXiv:0710.4304•Physical Review A•May 16, 2008•24 citations

Message passing and Monte Carlo algorithms: Connecting fixed points with metastable states

Alejandro Lage-Castellanos, Roberto Mulet, Federico Ricci‐Tersenghi

Mean field-like approximations (including naive mean field, Bethe and Kikuchi and more general Cluster Variational Methods) are known to stabilize ordered phases at temperatures higher than the thermodynamical transition. For example, in the Edwards-Anderson model in 2-dimensions these approximations predict a spin glass transition at finite $T$. Here we show that the spin glass solutions of the Cluster Variational Method (CVM) at plaquette level do describe well actual metastable states of the system. Moreover, we prove that these states can be used to predict non trivial statistical quantities, like the distribution of the overlap between two replicas. Our results support the idea that message passing algorithms can be helpful to accelerate Monte Carlo simulations in finite dimensional systems.

arXiv:1406.5373•Europhysics Letters (EPL)•Sep 1, 2014•11 citations

Parallel computing of Edwards–Anderson model

M.A. Padalko, Yuriy Shevchenko

An algorithm for parallel exact calculation of the ground state of a two-dimensional Edwards–Anderson model with free boundary conditions is given. The running time of the algorithm grows exponentially as the side of the lattice square increases. If one side of the lattice is fixed, the running time grows polynomially with increasing size of the other side. The method may find application in the theory of spin glasses, in the field of quantum computing. Performance data for the bimodal distribution is given. The distribution of spin bonds can be either bimodal or Gaussian. The method makes it possible to compute systems up to a size of 40x40.

Dal nevostochnyi Matematicheskii Zhurnal•Dec 10, 2021•0 citations

Haake–Lewenstein–Wilkens approach to spin-glasses revisited

Maciej Lewenstein, David Cirauqui, Miguel Ángel García-March +5 more

Abstract We revisit the Haake–Lewenstein–Wilkens approach to Edwards–Anderson (EA) model of Ising spin glass (SG) (Haake et al 1985 Phys. Rev. Lett. 55 2606). This approach consists in evaluation and analysis of the probability distribution of configurations of two replicas of the system, averaged over quenched disorder. This probability distribution generates squares of thermal copies of spin variables from the two copies of the systems, averaged over disorder, that is the terms that enter the standard definition of the original EA order parameter, q EA . We use saddle point/steepest descent (SPSD) method to calculate the average of the Gaussian disorder in higher dimensions. This approximate result suggest that q EA > 0 at 0 < T < T c in 3D and 4D. The case of 2D seems to be a little more subtle, since in the present approach energy increase for a domain wall competes with boundary/edge effects more strongly in 2D; still our approach predicts SG order at sufficiently low temperature. We speculate, how these predictions confirm/contradict widely spread opinions that: (i) There exist only one (up to the spin flip) ground state in EA model in 2D, 3D and 4D; (ii) there is (no) SG transition in 3D and 4D (2D). This paper is dedicated to the memories of Fritz Haake and Marek Cieplak.

arXiv:2203.02914•Journal of Physics A Mathematical and Theoretical•Oct 24, 2022•1 citation
Starting from a cluster variational method, and inspired by the correctness of the paramagnetic ansatz [at high temperatures in general, and at any temperature in the two-dimensional (2D) Edwards-Anderson (EA) model] we propose a message-passing algorithm--the dual algorithm--to estimate the marginal probabilities of spin glasses on finite-dimensional lattices. We use the EA models in 2D and 3D as benchmarks. The dual algorithm improves the Bethe approximation, and we show that in a wide range of temperatures (compared to the Bethe critical temperature) our algorithm compares very well with Monte Carlo simulations, with the double-loop algorithm, and with exact calculation of the ground state of 2D systems with bimodal and Gaussian interactions. Moreover, it is usually 100 times faster than other provably convergent methods, as the double-loop algorithm. In 2D and 3D the quality of the inference deteriorates only where the correlation length becomes very large, i.e., at low temperatures in 2D and close to the critical temperature in 3D.
We study the performance of different message passing algorithms in the two dimensional Edwards Anderson model. We show that the standard Belief Propagation (BP) algorithm converges only at high temperature to a paramagnetic solution. Then, we test a Generalized Belief Propagation (GBP) algorithm, derived from a Cluster Variational Method (CVM) at the plaquette level. We compare its performance with BP and with other algorithms derived under the same approximation: Double Loop (DL) and a two-ways message passing algorithm (HAK). The plaquette-CVM approximation improves BP in at least three ways: the quality of the paramagnetic solution at high temperatures, a better estimate (lower) for the critical temperature, and the fact that the GBP message passing algorithm converges also to non paramagnetic solutions. The lack of convergence of the standard GBP message passing algorithm at low temperatures seems to be related to the implementation details and not to the appearance of long range order. In fact, we prove that a gauge invariance of the constrained CVM free energy can be exploited to derive a new message passing algorithm which converges at even lower temperatures. In all its region of convergence this new algorithm is faster than HAK and DL by some orders of magnitude.
We present and solve the replica symmetric equations in the context of the replica cluster variational method for the 2D random bond Ising model (including the 2D Edwards–Anderson spin-glass model). First, we solve a linearized version of these equations to obtain the phase diagrams of the model on the square and triangular lattices. In both cases, the spin-glass transition temperatures and the multicritical point estimations improve largely over the Bethe predictions. Moreover, we show that this phase diagram is consistent with the behavior of inference algorithms on single instances of the problem. Finally, we present a method to consistently find approximate solutions to the equations in the glassy phase. The method is applied to the triangular lattice down to T = 0, also in the presence of an external field.
Belief propagation---a powerful heuristic method to solve inference problems involving a large number of random variables---was recently generalized to quantum theory. Like its classical counterpart, this algorithm is exact on trees when the appropriate independence conditions are met and is expected to provide reliable approximations when operated on loopy graphs. In this paper, we benchmark the performances of loopy quantum belief propagation (QBP) in the context of finite-temperature quantum many-body physics. Our results indicate that QBP provides reliable estimates of the high-temperature correlation function when the typical loop size in the graph is large. As such, it is suitable, e.g., for the study of quantum spin glasses on Bethe lattices and the decoding of sparse quantum error correction codes.
Mean field-like approximations (including naive mean field, Bethe and Kikuchi and more general Cluster Variational Methods) are known to stabilize ordered phases at temperatures higher than the thermodynamical transition. For example, in the Edwards-Anderson model in 2-dimensions these approximations predict a spin glass transition at finite TTT. Here we show that the spin glass solutions of the Cluster Variational Method (CVM) at plaquette level do describe well actual metastable states of the system. Moreover, we prove that these states can be used to predict non trivial statistical quantities, like the distribution of the overlap between two replicas. Our results support the idea that message passing algorithms can be helpful to accelerate Monte Carlo simulations in finite dimensional systems.
An algorithm for parallel exact calculation of the ground state of a two-dimensional Edwards–Anderson model with free boundary conditions is given. The running time of the algorithm grows exponentially as the side of the lattice square increases. If one side of the lattice is fixed, the running time grows polynomially with increasing size of the other side. The method may find application in the theory of spin glasses, in the field of quantum computing. Performance data for the bimodal distribution is given. The distribution of spin bonds can be either bimodal or Gaussian. The method makes it possible to compute systems up to a size of 40x40.
Abstract We revisit the Haake–Lewenstein–Wilkens approach to Edwards–Anderson (EA) model of Ising spin glass (SG) (Haake et al 1985 Phys. Rev. Lett. 55 2606). This approach consists in evaluation and analysis of the probability distribution of configurations of two replicas of the system, averaged over quenched disorder. This probability distribution generates squares of thermal copies of spin variables from the two copies of the systems, averaged over disorder, that is the terms that enter the standard definition of the original EA order parameter, q EA . We use saddle point/steepest descent (SPSD) method to calculate the average of the Gaussian disorder in higher dimensions. This approximate result suggest that q EA > 0 at 0 < T < T c in 3D and 4D. The case of 2D seems to be a little more subtle, since in the present approach energy increase for a domain wall competes with boundary/edge effects more strongly in 2D; still our approach predicts SG order at sufficiently low temperature. We speculate, how these predictions confirm/contradict widely spread opinions that: (i) There exist only one (up to the spin flip) ground state in EA model in 2D, 3D and 4D; (ii) there is (no) SG transition in 3D and 4D (2D). This paper is dedicated to the memories of Fritz Haake and Marek Cieplak.