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:2305.01874 · Physical Review Letters

Tensor Network Message Passing

Yijia Wang, Y. Zhang, Feng Ping Pan, Pan Zhang

Published Mar 15, 2024• 14 citations
arXivHTMLPDF

Abstract

When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called "tensor network message passing." This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.

DOI
10.1103/physrevlett.132.117401

Related papers

Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence

Siddhant Midha, Y. Zhang

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.

PRX Quantum•May 28, 2026•0 citations

Belief propagation for general graphical models with loops

Pedro Hack, Hitter, Jonas, Christian B. Mendl +1 more

There is an increasing interest in scaling tensor network methods through belief propagation (BP), as well as increasing the accuracy of BP through tensor network methods. We develop a unification framework that takes an arbitrary graphical model with loops and provides message passing update rules and inference equations. We show that recent state-of-the-art methods regarding tensors and BP, like block belief propagation and tensor network message passing, are special instances of our framework. From a practical perspective, we discuss how our framework can be useful to understand the benefits of scheduling in BP, and show how it can be used for decoding purposes in quantum error correction. We simulate the computation of marginals, internal energy, Shannon entropy and the partition function on synthetic topologies (Kagome lattice and lattices resembling quantum error-correcting codes) and a real world topology of a power grid. The results show orders of magnitude accuracy increases for modest computational overheads. For the marginals, for example, we show that our framework can achieve an accuracy improvement of more than six orders of magnitude over tensor network BP.

arXiv:2411.04957•Nov 7, 2024•0 citations

A Block Belief-Propagation Algorithm for the Contraction of Tensor-Networks

Nir Gutman

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.

quant-pharXiv:2603.13304•Mar 4, 2026•0 citations

Efficient tensor network simulation of quantum many-body physics on sparse graphs

Subhayan Sahu, Brian G. Swingle

We study tensor network states defined on an underlying graph which is sparsely connected. Generic sparse graphs are expander graphs with a high probability, and one can represent volume law entangled states efficiently with only polynomial resources. We find that message-passing inference algorithms such as belief propagation can lead to efficient computation of local expectation values for a class of tensor network states defined on sparse graphs. As applications, we study local properties of square root states, graph states, and also employ this method to variationally prepare ground states of gapped Hamiltonians defined on generic graphs. Using the variational method we study the phase diagram of the transverse field quantum Ising model defined on sparse expander graphs.

arXiv:2206.04701•Jun 9, 2022•6 citations

Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence

Siddhant Midha, Zhang, Yifan F.

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 \emph{cluster expansion} that systematically improves the BP approximation. We prove that the cluster expansion converges exponentially fast if an object called the \emph{loop contribution} 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 classical and quantum error-correcting codes and simulating quantum systems.

arXiv:2510.02290•Oct 2, 2025•0 citations

Belief Propagation and Tensor Network Expansions for Many-Body Quantum Systems: Rigorous Results and Fundamental Limits

Siddhant Midha, Grace M. Sommers, Joseph Tindall +1 more

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.

quant-pharXiv:2604.03228•Apr 6, 2026•0 citations
When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called "tensor network message passing." This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.
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.
There is an increasing interest in scaling tensor network methods through belief propagation (BP), as well as increasing the accuracy of BP through tensor network methods. We develop a unification framework that takes an arbitrary graphical model with loops and provides message passing update rules and inference equations. We show that recent state-of-the-art methods regarding tensors and BP, like block belief propagation and tensor network message passing, are special instances of our framework. From a practical perspective, we discuss how our framework can be useful to understand the benefits of scheduling in BP, and show how it can be used for decoding purposes in quantum error correction. We simulate the computation of marginals, internal energy, Shannon entropy and the partition function on synthetic topologies (Kagome lattice and lattices resembling quantum error-correcting codes) and a real world topology of a power grid. The results show orders of magnitude accuracy increases for modest computational overheads. For the marginals, for example, we show that our framework can achieve an accuracy improvement of more than six orders of magnitude over tensor network BP.
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.
We study tensor network states defined on an underlying graph which is sparsely connected. Generic sparse graphs are expander graphs with a high probability, and one can represent volume law entangled states efficiently with only polynomial resources. We find that message-passing inference algorithms such as belief propagation can lead to efficient computation of local expectation values for a class of tensor network states defined on sparse graphs. As applications, we study local properties of square root states, graph states, and also employ this method to variationally prepare ground states of gapped Hamiltonians defined on generic graphs. Using the variational method we study the phase diagram of the transverse field quantum Ising model defined on sparse expander graphs.
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 \emph{cluster expansion} that systematically improves the BP approximation. We prove that the cluster expansion converges exponentially fast if an object called the \emph{loop contribution} 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 classical and quantum error-correcting codes and simulating quantum systems.
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.