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:1904.03312 · Journal of Statistical Mechanics Theory and Experiment

The matrix product approximation for the dynamic cavity method

Thomas Barthel

Published Jan 1, 2020• 12 citations
arXivHTMLPDF

Abstract

Abstract Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages—conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Barthel et al (2018 Phys. Rev . E 97 010104 (R)), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber–Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.

DOI
10.1088/1742-5468/ab5701

Related papers

A matrix product algorithm for stochastic dynamics on locally tree-like graphs

Thomas Barthel, Caterina De Bacco, Silvio Franz

We describe and demonstrate an algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of a locally tree-like graph. Networks with cycles are treated in the framework of the cavity method. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. As we demonstrate at the example of Glauber dynamics, due to the absence of cancellation effects, observables with small expectation values can be evaluated reliably, allowing for the study of decay processes and temporal correlations.

Bulletin of the American Physical Society•Aug 13, 2015•5 citations

Matrix product algorithm for stochastic dynamics on networks applied to nonequilibrium Glauber dynamics

Thomas Barthel, Caterina De Bacco, Silvio Franz

We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

arXiv:1508.03295•Physical review. E•Jan 29, 2018•20 citations

The cavity method for in and out of equilibrium systems on diluted graphs

Stefano Crotti

This work explores the cavity method from statistical physics as applied to systems of variables interacting on diluted graphs.The cavity approximation, originally conceived for studying disordered systems like spin glasses, has evolved into a versatile framework, providing message-passing algorithms such as belief propagation.Here we consider both static (equilibrium) and dynamic (non-equilibrium) scenarios, exploiting the effectiveness of the cavity approach in its analytical as well as algorithmic variations.The first chapter introduces the mathematical formulation of the cavity method as originated in physics and then re-invented in the fields of communications and computer science.In chapter two we study the closest vector problem, a prototypical task in discrete optimization with applications in cryptography and the theory of computational complexity.By means of a mapping to a spin glass model, the cavity method provides semi-analytical results for an infinite-size system.These are then compared with the outcome of approximate optimization on finite instances.Of particular interest is the interplay between phase transitions in the geometry of the space of solutions and the performance of optimization algorithms.In the third chapter, devoted to non-equilibrium dynamics, we introduce and develop the Matrix Product Belief Propagation (MPBP) algorithm for computing observables of Markov processes on graphs.We consider how reweighting a process, an operation which arises naturally when considering inverse problems and atypical trajectories, can lead to major computational challenges.By leveraging the matrix product state approximation from quantum mechanics, MPBP reduces computational complexity while maintaining high accuracy for dynamical models such as epidemic spreading and Glauber dynamics.vi Finally, chapter four contains ongoing work on an extension of MPBP able to describe the steady state of stochastic processes on graphs.This is done by exploiting the Uniform Matrix Product State (UMPS) formalism originally formulated for homogeneous one-dimensional quantum systems.

•Jan 17, 2025•0 citations

Matrix-Product Belief Propagation for continuous-state-space variables

Federico Florio, Alfredo Braunstein

Computation of observables in discrete stochastic, possibly conditioned, dynamics over large sparse networks is fundamental for a myriad of applications. The Matrix-Product Belief Propagation method allows a semi-analytical estimation of such observables in tree-like networks with a controlled error that depends on the bond dimension, that is the dimension of the employed square matrices. Its computational cost is linear in the time horizon and the network size for a large family of models with discrete degrees of freedom. Here, a generalization of this method to models with continuous or mixed continuous/discrete degrees of freedom is presented, using a tunable expansion in a Hilbert function basis. For a wide class of models, the computational cost of the method is linear in the network size with a prefactor that depends on the basis size and the bond dimension. The method's efficacy is demonstrated by employing a Fourier basis for a mixed continuous/discrete representation of the Kinetic Ising dynamics with real-valued random couplings, where intermediate "local fields" are treated as continuous. The accuracy of the method is verified via comparison with Monte Carlo simulations. For this model, we calculate time auto-correlations, time evolution of energy and magnetization, and finally we estimate the large deviation function of the magnetization at a given future time.

arXiv:2605.14522•May 14, 2026•0 citations

CT-bMPS: Approximate Tensor Network Contraction with Boundary MPS on Contraction Trees

Hidetaka Manabe, Feng Pan

We introduce contraction tree boundary matrix product states (CT-bMPS), a scalable approximate contraction method for general closed tensor networks. CT-bMPS represents the boundary tensor and its complementary environment at each edge of a contraction tree as matrix product states. This representation allows local compression based on a reduced transition matrix to incorporate environment information along arbitrary contraction trees, while keeping the time and memory costs polynomial in the network size and bond dimension. We benchmark the method on a variety of models and applications, including Ising partition functions, random tensor networks, kicked Ising dynamics, and quantum error correction decoding. These benchmarks demonstrate improved accuracy and computational efficiency over existing general-purpose approximate contraction methods, together with the ability to handle larger and more complex networks. Optimized contraction trees and environment updates substantially improve accuracy without increasing the bond dimension. These results establish CT-bMPS as a general and scalable approximation framework with flexible contraction orders and environment-based compression for a wide range of applications.

quant-pharXiv:2610.06574•Oct 6, 2026•0 citations

Nonequilibrium steady-state dynamics of Markov processes on graphs

Stefano Crotti, Thomas Barthel, Alfredo Braunstein

We propose an analytic approach for the steady-state dynamics of Markov processes on locally tree-like graphs. It is based on time-translation invariant probability distributions for edge trajectories, which we encode in terms of infinite matrix products. For homogeneous ensembles on regular graphs, the distribution is parametrized by a single d× d× r^2 d × d × r 2 tensor, where r r is the number of states per variable, and d d is the matrix-product bond dimension. While the method becomes exact in the large- d d limit, it typically provides highly accurate results even for small bond dimensions d d . The d^2r^2 d 2 r 2 parameters are determined by solving a fixed point equation, for which we provide an efficient belief-propagation procedure. We apply this approach to a variety of models, including Ising-Glauber dynamics with symmetric and asymmetric couplings, as well as the SIS model. Even for small d d , the results are compatible with Monte Carlo estimates and accurately reproduce known exact solutions. The method provides access to precise temporal correlations, which, in some regimes, would be virtually impossible to estimate by sampling.

arXiv:2411.19100•SciPost Physics•Aug 18, 2025•2 citations
Abstract Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages—conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Barthel et al (2018 Phys. Rev . E 97 010104 (R)), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber–Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.
We describe and demonstrate an algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of a locally tree-like graph. Networks with cycles are treated in the framework of the cavity method. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. As we demonstrate at the example of Glauber dynamics, due to the absence of cancellation effects, observables with small expectation values can be evaluated reliably, allowing for the study of decay processes and temporal correlations.
We introduce and apply an efficient method for the precise simulation of stochastic dynamical processes on locally treelike graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, our approach is based on a matrix product approximation of the so-called edge messages-conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both single instances as well as the thermodynamic limit. We employ it to examine prototypical nonequilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.
This work explores the cavity method from statistical physics as applied to systems of variables interacting on diluted graphs.The cavity approximation, originally conceived for studying disordered systems like spin glasses, has evolved into a versatile framework, providing message-passing algorithms such as belief propagation.Here we consider both static (equilibrium) and dynamic (non-equilibrium) scenarios, exploiting the effectiveness of the cavity approach in its analytical as well as algorithmic variations.The first chapter introduces the mathematical formulation of the cavity method as originated in physics and then re-invented in the fields of communications and computer science.In chapter two we study the closest vector problem, a prototypical task in discrete optimization with applications in cryptography and the theory of computational complexity.By means of a mapping to a spin glass model, the cavity method provides semi-analytical results for an infinite-size system.These are then compared with the outcome of approximate optimization on finite instances.Of particular interest is the interplay between phase transitions in the geometry of the space of solutions and the performance of optimization algorithms.In the third chapter, devoted to non-equilibrium dynamics, we introduce and develop the Matrix Product Belief Propagation (MPBP) algorithm for computing observables of Markov processes on graphs.We consider how reweighting a process, an operation which arises naturally when considering inverse problems and atypical trajectories, can lead to major computational challenges.By leveraging the matrix product state approximation from quantum mechanics, MPBP reduces computational complexity while maintaining high accuracy for dynamical models such as epidemic spreading and Glauber dynamics.vi Finally, chapter four contains ongoing work on an extension of MPBP able to describe the steady state of stochastic processes on graphs.This is done by exploiting the Uniform Matrix Product State (UMPS) formalism originally formulated for homogeneous one-dimensional quantum systems.
Computation of observables in discrete stochastic, possibly conditioned, dynamics over large sparse networks is fundamental for a myriad of applications. The Matrix-Product Belief Propagation method allows a semi-analytical estimation of such observables in tree-like networks with a controlled error that depends on the bond dimension, that is the dimension of the employed square matrices. Its computational cost is linear in the time horizon and the network size for a large family of models with discrete degrees of freedom. Here, a generalization of this method to models with continuous or mixed continuous/discrete degrees of freedom is presented, using a tunable expansion in a Hilbert function basis. For a wide class of models, the computational cost of the method is linear in the network size with a prefactor that depends on the basis size and the bond dimension. The method's efficacy is demonstrated by employing a Fourier basis for a mixed continuous/discrete representation of the Kinetic Ising dynamics with real-valued random couplings, where intermediate "local fields" are treated as continuous. The accuracy of the method is verified via comparison with Monte Carlo simulations. For this model, we calculate time auto-correlations, time evolution of energy and magnetization, and finally we estimate the large deviation function of the magnetization at a given future time.
We introduce contraction tree boundary matrix product states (CT-bMPS), a scalable approximate contraction method for general closed tensor networks. CT-bMPS represents the boundary tensor and its complementary environment at each edge of a contraction tree as matrix product states. This representation allows local compression based on a reduced transition matrix to incorporate environment information along arbitrary contraction trees, while keeping the time and memory costs polynomial in the network size and bond dimension. We benchmark the method on a variety of models and applications, including Ising partition functions, random tensor networks, kicked Ising dynamics, and quantum error correction decoding. These benchmarks demonstrate improved accuracy and computational efficiency over existing general-purpose approximate contraction methods, together with the ability to handle larger and more complex networks. Optimized contraction trees and environment updates substantially improve accuracy without increasing the bond dimension. These results establish CT-bMPS as a general and scalable approximation framework with flexible contraction orders and environment-based compression for a wide range of applications.
We propose an analytic approach for the steady-state dynamics of Markov processes on locally tree-like graphs. It is based on time-translation invariant probability distributions for edge trajectories, which we encode in terms of infinite matrix products. For homogeneous ensembles on regular graphs, the distribution is parametrized by a single d× d× r^2 d × d × r 2 tensor, where r r is the number of states per variable, and d d is the matrix-product bond dimension. While the method becomes exact in the large- d d limit, it typically provides highly accurate results even for small bond dimensions d d . The d^2r^2 d 2 r 2 parameters are determined by solving a fixed point equation, for which we provide an efficient belief-propagation procedure. We apply this approach to a variety of models, including Ising-Glauber dynamics with symmetric and asymmetric couplings, as well as the SIS model. Even for small d d , the results are compatible with Monte Carlo estimates and accurately reproduce known exact solutions. The method provides access to precise temporal correlations, which, in some regimes, would be virtually impossible to estimate by sampling.