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:1406.5373 · Europhysics Letters (EPL)

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

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

Published Sep 1, 2014• 10 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1209/0295-5075/107/57011

Related papers

Random field Ising model in two dimensions: Bethe approximation, cluster variational method and message passing algorithms

Eduardo Domínguez, Alejandro Lage-Castellanos, Roberto Mulet

Abstract We study two free energy approximations (Bethe and plaquette-CVM) for the Random Field Ising Model in two dimensions. We compare results obtained by these two methods in single instances of the model on the square grid, showing the difficulties arising in defining a robust critical line. We also attempt average case calculations using a replica-symmetric ansatz, and compare the results with single instances. Both, Bethe and plaquette-CVM approximations present a similar panorama in the phase space, predicting long range order at low temperatures and fields. We show that plaquette-CVM is more precise, in the sense that predicts a lower critical line (the truth being no line at all). Furthermore, we give some insight on the non-trivial structure of the fixed points of different message passing algorithms. A study of the Monte Carlo dynamics for an arbitrary sample shows that GBP states are very well correlated with states that are attractors of the stochastic dynamics.

arXiv:1501.07545•Journal of Statistical Mechanics Theory and Experiment•Jul 1, 2015•5 citations

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

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

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.

arXiv:1102.3305•Physical Review E•Oct 24, 2011•11 citations

Quantum cluster variational method and message passing algorithms revisited

Eduardo Domínguez, Roberto Mulet

We present a general framework to study quantum disordered systems in the context of the Kikuchi's cluster variational method (CVM). The method relies in the solution of message passing-like equations for single instances or in the iterative solution of complex population dynamic algorithms for an average case scenario. We first show how a standard application of the Kikuchi's CVM can be easily translated to message passing equations for specific instances of the disordered system. We then present an ``ad hoc'' extension of these equations to a population dynamic algorithm representing an average case scenario. At the Bethe level, these equations are equivalent to the dynamic population equations that can be derived from a proper cavity ansatz. However, at the plaquette approximation, the interpretation is more subtle and we discuss it taking also into account previous results in classical disordered models. Moreover, we develop a formalism to properly deal with the average case scenario using a replica-symmetric ansatz within this CVM for quantum disordered systems. Finally, we present and discuss numerical solutions of the different approximations for the quantum transverse Ising model and the quantum random field Ising model in two-dimensional lattices.

arXiv:1710.08871•Physical review. B./Physical review. B•Feb 14, 2018•3 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•19 citations

Ising spin glass: Replica-symmetric cluster expansion in finite dimensions

Anil Khurana

The replica-symmetric cluster expansion for the Ising spin glass is reviewed and explained. The expansion allows computation of various quantities and correlations directly in finite dimensions, without recourse to the mean-field theory or the saddle point. The expansion for the free energy is recovered with the use of external fields that couple to the replica-symmetric Edwards-Anderson order parameter. The expansion scheme is applied to the Edwards-Anderson susceptibility. The expansion diverges in the mean-field [infinite dimensionality] limit. The divergent expansion, when naively summed, yields the negative replicon mass of the mean-field theory. This so-called Almeida-Thouless instability of the replica-symmetric mean-field theory is argued to be absent in finite dimensions. The argument, similar to the one already reported for the entropy, depends on the low-temperature behavior of terms in the expansion at finite dimensions. \textcopyright{} 1996 The American Physical Society.

Physical review. B, Condensed matter•Sep 1, 1996•2 citations

Influence of critical behavior on the spin-glass phase

Hemant Bokil, Barbara Drossel, M A Moore

We have argued in recent papers that the Monte Carlo results for the equilibrium properties of the Edwards-Anderson spin glass in three dimensions, which had been interpreted earlier as providing evidence for replica symmetry breaking, can be explained quite simply within the droplet model once finite-size effects and proximity to the critical point are taken into account. In this paper we show that similar considerations are sufficient to explain the Monte Carlo data in four dimensions. In particular, we study the Parisi overlap and the link overlap for the four-dimensional Ising spin glass in the Migdal-Kadanoff approximation. Similar to what is seen in three dimensions, we find that temperatures well below those studied in the Monte Carlo simulations have to be reached before the droplet model predictions become apparent. We also show that the double-peak structure of the link overlap distribution function is related to the difference between domain-wall excitations that cross the entire system and droplet excitations that are confined to a smaller region.

arXiv:cond-mat/0002130•Physical review. B, Condensed matter•Jul 1, 2000•24 citations
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.
Abstract We study two free energy approximations (Bethe and plaquette-CVM) for the Random Field Ising Model in two dimensions. We compare results obtained by these two methods in single instances of the model on the square grid, showing the difficulties arising in defining a robust critical line. We also attempt average case calculations using a replica-symmetric ansatz, and compare the results with single instances. Both, Bethe and plaquette-CVM approximations present a similar panorama in the phase space, predicting long range order at low temperatures and fields. We show that plaquette-CVM is more precise, in the sense that predicts a lower critical line (the truth being no line at all). Furthermore, we give some insight on the non-trivial structure of the fixed points of different message passing algorithms. A study of the Monte Carlo dynamics for an arbitrary sample shows that GBP states are very well correlated with states that are attractors of the stochastic dynamics.
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 present a general framework to study quantum disordered systems in the context of the Kikuchi's cluster variational method (CVM). The method relies in the solution of message passing-like equations for single instances or in the iterative solution of complex population dynamic algorithms for an average case scenario. We first show how a standard application of the Kikuchi's CVM can be easily translated to message passing equations for specific instances of the disordered system. We then present an ``ad hoc'' extension of these equations to a population dynamic algorithm representing an average case scenario. At the Bethe level, these equations are equivalent to the dynamic population equations that can be derived from a proper cavity ansatz. However, at the plaquette approximation, the interpretation is more subtle and we discuss it taking also into account previous results in classical disordered models. Moreover, we develop a formalism to properly deal with the average case scenario using a replica-symmetric ansatz within this CVM for quantum disordered systems. Finally, we present and discuss numerical solutions of the different approximations for the quantum transverse Ising model and the quantum random field Ising model in two-dimensional lattices.
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.
The replica-symmetric cluster expansion for the Ising spin glass is reviewed and explained. The expansion allows computation of various quantities and correlations directly in finite dimensions, without recourse to the mean-field theory or the saddle point. The expansion for the free energy is recovered with the use of external fields that couple to the replica-symmetric Edwards-Anderson order parameter. The expansion scheme is applied to the Edwards-Anderson susceptibility. The expansion diverges in the mean-field [infinite dimensionality] limit. The divergent expansion, when naively summed, yields the negative replicon mass of the mean-field theory. This so-called Almeida-Thouless instability of the replica-symmetric mean-field theory is argued to be absent in finite dimensions. The argument, similar to the one already reported for the entropy, depends on the low-temperature behavior of terms in the expansion at finite dimensions. \textcopyright{} 1996 The American Physical Society.
We have argued in recent papers that the Monte Carlo results for the equilibrium properties of the Edwards-Anderson spin glass in three dimensions, which had been interpreted earlier as providing evidence for replica symmetry breaking, can be explained quite simply within the droplet model once finite-size effects and proximity to the critical point are taken into account. In this paper we show that similar considerations are sufficient to explain the Monte Carlo data in four dimensions. In particular, we study the Parisi overlap and the link overlap for the four-dimensional Ising spin glass in the Migdal-Kadanoff approximation. Similar to what is seen in three dimensions, we find that temperatures well below those studied in the Monte Carlo simulations have to be reached before the droplet model predictions become apparent. We also show that the double-peak structure of the link overlap distribution function is related to the difference between domain-wall excitations that cross the entire system and droplet excitations that are confined to a smaller region.