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:2510.02290

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

Siddhant Midha, Zhang, Yifan F.

Published Oct 2, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2510.02290

Related papers

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

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

Partitioned Expansions for Approximate Tensor Network Contractions

Glen Evenbly, Johnnie Gray, Garnet Kin-Lic Chan

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.

quant-pharXiv:2512.10910•Dec 12, 2025•0 citations

Algorithmic Locality of Quantum Tensor Network Belief Propagation

Siddhant Midha, Yifan F. Zhang, Daniel Malz +2 more

Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to $1/\mathrm{poly}(N)$ error in $\mathrm{poly}(N)$ time for an $N$ qubit system. We further identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. We exhibit three regimes admitting strong injectivity: random Gaussian PEPS with large physical dimension, high-temperature Gibbs states of commuting two-body Hamiltonians, and fixed-depth quantum circuits subject to sufficiently strong depolarizing noise. Our bounds are worst-case sufficient conditions and do not identify sharp algorithmic transitions.

quant-pharXiv:2604.21919•Apr 24, 2026•0 citations

Loop series expansions for tensor networks

Glen Evenbly, Nicola Pancotti, Ashley Milsted +2 more

Belief propagation (BP) can be a useful tool to approximately contract a tensor network, provided that the contributions from any closed loops in the network are sufficiently weak. In this article, we describe how a loop series expansion can be applied to systematically improve the accuracy of a BP approximation to a tensor network contraction, in principle converging arbitrarily close to the exact result. More generally, our result provides a framework for expanding a tensor network as a sum of component networks in a hierarchy of increasing complexity. We benchmark this proposal for the contraction of infinite projected entangled pair states, either representing the ground state of an Affleck-Kennedy-Lieb-Tasaki (AKLT) model or with randomly defined tensors, where it is shown to improve in accuracy over standard BP by several orders of magnitude while incurring only a minor increase in computational cost. These results indicate that the proposed series expansions could be a useful tool to accurately evaluate tensor networks in cases that otherwise exceed the limits of established contraction routines.

arXiv:2409.03108•Physical Review Research•Jan 13, 2026•6 citations

Stochastic Loop Corrections to Belief Propagation for Tensor Network Contraction

Gi Beom Sim, Tae Hyeon Park, Kwang S. Kim +6 more

Tensor network contraction is a fundamental computational challenge underlying quantum many-body physics, statistical mechanics, and machine learning. Belief propagation (BP) provides an efficient approximate solution, but introduces systematic errors on graphs with loops. Here, we introduce a hybrid method that achieves accurate results by stochastically sampling loop corrections to BP and showcase our method by applying it to the two-dimensional ferromagnetic Ising model. For any pairwise Markov random field with symmetric edge potentials, our approach exploits an exact factorization of the partition function into the BP contribution and a loop correction factor summing over all valid loop configurations, weighted by edge weights derived directly from the potentials. We sample this sum using Markov chain Monte Carlo with moves that preserve the loop constraint, combined with umbrella sampling to ensure efficient exploration across all correlation strengths. Our stochastic approach provides unbiased estimates with controllable statistical error in any parameter regime.

cond-mat.str-elCross-listedarXiv:2603.08427•Mar 10, 2026•0 citations
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.
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.
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.
Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to 1/poly(N)1/\mathrm{poly}(N)1/poly(N) error in poly(N)\mathrm{poly}(N)poly(N) time for an NNN qubit system. We further identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. We exhibit three regimes admitting strong injectivity: random Gaussian PEPS with large physical dimension, high-temperature Gibbs states of commuting two-body Hamiltonians, and fixed-depth quantum circuits subject to sufficiently strong depolarizing noise. Our bounds are worst-case sufficient conditions and do not identify sharp algorithmic transitions.
Belief propagation (BP) can be a useful tool to approximately contract a tensor network, provided that the contributions from any closed loops in the network are sufficiently weak. In this article, we describe how a loop series expansion can be applied to systematically improve the accuracy of a BP approximation to a tensor network contraction, in principle converging arbitrarily close to the exact result. More generally, our result provides a framework for expanding a tensor network as a sum of component networks in a hierarchy of increasing complexity. We benchmark this proposal for the contraction of infinite projected entangled pair states, either representing the ground state of an Affleck-Kennedy-Lieb-Tasaki (AKLT) model or with randomly defined tensors, where it is shown to improve in accuracy over standard BP by several orders of magnitude while incurring only a minor increase in computational cost. These results indicate that the proposed series expansions could be a useful tool to accurately evaluate tensor networks in cases that otherwise exceed the limits of established contraction routines.
Tensor network contraction is a fundamental computational challenge underlying quantum many-body physics, statistical mechanics, and machine learning. Belief propagation (BP) provides an efficient approximate solution, but introduces systematic errors on graphs with loops. Here, we introduce a hybrid method that achieves accurate results by stochastically sampling loop corrections to BP and showcase our method by applying it to the two-dimensional ferromagnetic Ising model. For any pairwise Markov random field with symmetric edge potentials, our approach exploits an exact factorization of the partition function into the BP contribution and a loop correction factor summing over all valid loop configurations, weighted by edge weights derived directly from the potentials. We sample this sum using Markov chain Monte Carlo with moves that preserve the loop constraint, combined with umbrella sampling to ensure efficient exploration across all correlation strengths. Our stochastic approach provides unbiased estimates with controllable statistical error in any parameter regime.