The cluster variation method has been developed into a general theoretical framework for treating short-range correlations in many-body systems after it was first proposed by Kikuchi in 1951. On the numerical side, a message-passing approach called generalized belief propagation (GBP) was proposed by Yedidia, Freeman and Weiss about a decade ago as a way of computing the minimal value of the cluster variational free energy and the marginal distributions of clusters of variables. However the GBP equations are often redundant, and it is quite a non-trivial task to make the GBP iteration converges to a fixed point. These drawbacks hinder the application of the GBP approach to finite-dimensional frustrated and disordered systems. In this work we report an alternative and simple derivation of the GBP equations starting from the partition function. Based on this derivation we propose a natural and systematic way of removing the redundance of the GBP equations. We apply the simplified generalized belief propagation (SGBP) equations to the two-dimensional and the three-dimensional ferromagnetic Ising model and Edwards-Anderson spin glass model. The numerical results confirm that the SGBP message-passing approach is able to achieve satisfactory performance on these model systems. We also suggest that a subset of the SGBP equations can be neglected in the numerical iteration process without affecting the final results.
The cluster variation method has been developed into a general theoretical framework for treating short-range correlations in many-body systems after it was first proposed by Kikuchi in 1951. On the numerical side, a message-passing approach called generalized belief propagation (GBP) was proposed by Yedidia, Freeman and Weiss about a decade ago as a way of computing the minimal value of the cluster variational free energy and the marginal distributions of clusters of variables. However the GBP equations are often redundant, and it is quite a non-trivial task to make the GBP iteration converges to a fixed point. These drawbacks hinder the application of the GBP approach to finite-dimensional frustrated and disordered systems. In this work we report an alternative and simple derivation of the GBP equations starting from the partition function. Based on this derivation we propose a natural and systematic way of removing the redundance of the GBP equations. We apply the simplified generalized belief propagation (SGBP) equations to the two-dimensional and the three-dimensional ferromagnetic Ising model and Edwards-Anderson spin glass model. The numerical results confirm that the SGBP message-passing approach is able to achieve satisfactory performance on these model systems. We also suggest that a subset of the SGBP equations can be neglected in the numerical iteration process without affecting the final results.
Recent years have seen a growing interest in the use of belief propagation - an algorithm originally introduced for performing statistical inference on graphical models - for approximate, but highly efficient, tensor network contraction. Here, we detail how to apply generalized belief propagation (GBP) - where messages are passed within a hierarchy of overlapping regions of the tensor network - to approximately contract tensor networks and obtain accurate results. The original belief propagation algorithm is a corner case of this approach, corresponding to a particularly simple choice of regions of the tensor network. We implement the GBP algorithm for a number of different region choices on a range of two- and three-dimensional, infinite and finite tensor networks, solving the corresponding fixed point equations both numerically and, in certain tractable cases, analytically. Our examples include calculating the partition function of the fully frustrated Ising model, computing the ground state degeneracy of three-dimensional ice models, measuring observables on the deformed AKLT quantum state and evaluating the norm of randomly generated tensor network states.
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.
A new approximation of the cluster variational method is introduced for the three-dimensional Ising model on the simple cubic lattice . The maximal cluster is, as far as we know, the largest ever used in this method. A message-passing algorithm, generalized belief propagation, is used to minimize the variational free energy . Convergence properties and performance of the algorithm are investigated. The approximation is used to compute the spontaneous magnetization , which is then compared to previous results. Using the present results as the last step in a sequence of three cluster variational approximations, an extrapolation is obtained which captures the leading critical behavior with a good accuracy.
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.
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.
Belief propagation (BP) provides a scalable heuristic for contracting tensor networks on loopy graphs, but its success in quantum many-body settings has largely rested on empirical evidence. Developing upon a recently introduced cluster-expansion framework for tensor networks, we rigorously study the applicability of BP to many-body quantum systems. For a state represented as a PEPS satisfying a ``loop-decay" condition, we prove that BP supplemented by cluster corrections approximates local observables with exponentially small relative error, and we give explicit formulas expressing local expectation values as BP predictions dressed by connected clusters intersecting the observable region. This representation establishes a direct link between cluster corrections and physical correlation functions. As a result, we show that ``loop-decay" \emph{necessarily implies} exponential decay of connected correlations, yielding sharp, rigorous criteria for when BP can and cannot succeed, and ruling out its validity at critical points. Numerical simulations of the two- and three-dimensional transverse field Ising model at zero and finite temperature confirm our analytical predictions, demonstrating quantitative accuracy deep in gapped phases and systematic failure near criticality.