We introduce "matrix product belief propagation" (MP-BP) as a controlled method for the approximate contraction of two-dimensional tensor networks and graphical models, which generically leads to a quadratic reduction of errors relative to existing methods: at similar computational effort, the number of accurate digits is asymptotically doubled. For infinite systems, MP-BP can be understood as a practical implementation of Baxter's corner-transfer-matrix method; for reflection-symmetric networks, it further coincides with the boundary matrix-product-state and corner-transfer-matrix renormalization group algorithms as conventionally implemented. In the limit of unit matrix-product rank, MP-BP is equivalent to belief propagation, and more generally, can be understood as a generalization of BP in which the "messages" live on surfaces and are assumed to have a matrix-product factorization. We further extend the quadratic improvement to the computation of expectation values, and numerically demonstrate the qualitatively improved convergence for a variety of classical and quantum 2D tensor network problems.
We introduce "matrix product belief propagation" (MP-BP) as a controlled method for the approximate contraction of two-dimensional tensor networks and graphical models, which generically leads to a quadratic reduction of errors relative to existing methods: at similar computational effort, the number of accurate digits is asymptotically doubled. For infinite systems, MP-BP can be understood as a practical implementation of Baxter's corner-transfer-matrix method; for reflection-symmetric networks, it further coincides with the boundary matrix-product-state and corner-transfer-matrix renormalization group algorithms as conventionally implemented. In the limit of unit matrix-product rank, MP-BP is equivalent to belief propagation, and more generally, can be understood as a generalization of BP in which the "messages" live on surfaces and are assumed to have a matrix-product factorization. We further extend the quadratic improvement to the computation of expectation values, and numerically demonstrate the qualitatively improved convergence for a variety of classical and quantum 2D tensor network problems.
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.
Simulating many-body quantum systems on a classical computer is difficult due to the large number of degrees of freedom, causing the computational complexity to grow exponentially with system size. Tensor Networks (TN) is a framework that breaks down large tensors into a network of smaller tensors, enabling efficient simulation of certain many-body quantum systems. To calculate expectation values of local observables or simulate nearest-neighbor interactions, a contraction of the entire network is needed. This is a known hard problem, which cannot be done exactly for systems with spatial dimension D>1 and is the major bottleneck in all tensor-network based algorithms. Various approximate-contraction algorithms have been suggested, all with their strengths and weaknesses. Nevertheless, contracting a 2D TN remains a major numerical challenge, limiting the use of TN techniques for many interesting systems.
Recently, a close connection between TN and Probabilistic Graphical Models (PGM) has been shown. In the PGM framework, marginals of complicated probability distributions can be approximated using iterative message passing algorithms such as Belief Propagation (BP). The BP algorithm can be adapted to the TN framework as an efficient contraction algorithm. While BP is extremely efficient and easy to parallelize, it often yields inaccurate results for highly correlated quantum states or frustrated systems. To overcome this, we suggest the BlockBP algorithm, which coarse-grains the system into blocks and performs BP between them.
This thesis focuses on: (i) development and implementation of the BlockBP algorithm for infinite lattices; (ii) using this algorithm to study the anti-ferromagnetic Heisenberg model on the Kagome lattice in the thermodynamic limit - a frustrated 2D model that is difficult to simulate using existing numerical methods.
Belief propagation is a well-studied algorithm for approximating local marginals of multivariate probability distribution over complex networks, while tensor network states are powerful tools for quantum and classical many-body problems. Building on a recent connection between the belief propagation algorithm and the problem of tensor network contraction, we propose a block belief propagation algorithm for contracting two-dimensional (2D) tensor networks and approximating the ground state of 2D systems. The advantages of our method are threefold: (1) the same algorithm works for both finite and infinite systems; (2) it allows natural and efficient parallelization; and (3) given its flexibility, it would allow us to deal with different unit cells. As applications, we use our algorithm to study the 2D Heisenberg and transverse Ising models, and show that the accuracy of the method is on par with state-of-the-art results.
We propose a method for approximating the contraction of a tensor network by partitioning the network into a sum of computationally cheaper networks. This method, which we call a partitioned network expansion (PNE), builds upon recent work that systematically improves belief propagation (BP) approximations using loop corrections. However, in contrast to previous approaches, our expansion does not require a known BP fixed point to be implemented and can still yield accurate results even in cases where BP fails entirely. The flexibility of our approach is demonstrated through applications to a variety of example networks, including finite 2D and 3D networks, infinite networks, networks with open indices, and networks with degenerate BP fixed points. Benchmark numerical results for networks composed of Ising, AKLT, and random tensors typically show an improvement in accuracy over BP by several orders of magnitude (when BP solutions are obtainable) and also demonstrate improved performance over traditional network approximations based on singular value decomposition (SVD) for certain tasks.
Tensor network contraction on arbitrary graphs is a fundamental computational challenge with applications ranging from quantum simulation to error correction. While belief propagation (BP) provides a powerful approximation algorithm for this task, its accuracy limitations are poorly understood and systematic improvements remain elusive. Here, we develop a rigorous theoretical framework for BP in tensor networks, leveraging insights from statistical mechanics to devise a that systematically improves the BP approximation. We prove that the cluster expansion converges exponentially fast if an object called the decays sufficiently fast with the loop size, giving a rigorous error bound on BP. We also provide a simple and efficient algorithm to compute the cluster expansion to arbitrary order. We demonstrate the efficacy of our method on the two-dimensional Ising model, where we find that our method significantly improves upon BP and existing corrective algorithms such as loop series expansion. Our work opens the door to a systematic theory of BP for tensor networks and its applications in decoding quantum error-correcting codes and simulating quantum systems.
Tensor networks have attracted much attention as a powerful tool for modeling quantum many-body systems. Their contraction is a significant challenge, however, especially in highly connected networks, as memory requirements become prohibitive and the optimal contraction order is increasingly hard to find. The belief propagation (BP) algorithm has emerged as an alternative to exact contraction. Being formulated in a graph-agnostic way, it offers great flexibility, but its accuracy suffers in the presence of loops. In this work, we combine BP with the DMRG algorithm to solve ground-state problems, thereby extending DMRG to higher dimensions and arbitrary lattices. We demonstrate the viability of BP-DMRG on the transverse-field Ising model on a 2×2 hexagonal lattice, finding that it produces states with a fidelity between 0.9 and 0.99 to the true ground state, and energy estimates with a relative error between 10−2 and 10−3. Additionally, BP-DMRG can find ground states on randomly generated lattices, with fidelity improving as the transverse field increases. We conclude with a discussion of the limitations we encounter when using belief propagation, highlighting that the TFI tensor network operators lead to larger errors during BP iterations in BP-DMRG.