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

Bulletin of the American Physical Society

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

Thomas Barthel, Caterina De Bacco, Silvio Franz

Published Aug 13, 2015• 5 citations
OpenAlex

Abstract

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.

Related papers

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 matrix product approximation for the dynamic cavity method

Thomas Barthel

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.

arXiv:1904.03312•Journal of Statistical Mechanics Theory and Experiment•Jan 1, 2020•12 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

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

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

Simulating strongly correlated quantum systems with tree tensor networks

V. Murg, Frank Verstraete, Örs Legeza +1 more

We present a tree-tensor-network-based method to study strongly correlated systems with nonlocal interactions in higher dimensions. Although the momentum-space and quantum-chemistry versions of the density-matrix renormalization group (DMRG) method have long been applied to such systems, the spatial topology of DMRG-based methods allows efficient optimizations to be carried out with respect to one spatial dimension only. Extending the matrix-product-state picture, we formulate a more general approach by allowing the local sites to be coupled to more than two neighboring auxiliary subspaces. Following [Y. Shi, L. Duan, and G. Vidal, Phys. Rev. A 74, 022320 (2006)], we treat a treelike network ansatz with arbitrary coordination number $z$, where the $z=2$ case corresponds to the one-dimensional (1D) scheme. For this ansatz, the long-range correlation deviates from the mean-field value polynomially with distance, in contrast to the matrix-product ansatz, which deviates exponentially. The computational cost of the tree-tensor-network method is significantly smaller than that of previous DMRG-based attempts, which renormalize several blocks into a single block. In addition, we investigate the effect of unitary transformations on the local basis states and present a method for optimizing such transformations. For the 1D interacting spinless fermion model, the optimized transformation interpolates smoothly between real space and momentum space. Calculations carried out on small quantum chemical systems support our approach.

arXiv:1006.3095•Physical Review B•Nov 3, 2010•270 citations
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.
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 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.
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.
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.
We present a tree-tensor-network-based method to study strongly correlated systems with nonlocal interactions in higher dimensions. Although the momentum-space and quantum-chemistry versions of the density-matrix renormalization group (DMRG) method have long been applied to such systems, the spatial topology of DMRG-based methods allows efficient optimizations to be carried out with respect to one spatial dimension only. Extending the matrix-product-state picture, we formulate a more general approach by allowing the local sites to be coupled to more than two neighboring auxiliary subspaces. Following [Y. Shi, L. Duan, and G. Vidal, Phys. Rev. A 74, 022320 (2006)], we treat a treelike network ansatz with arbitrary coordination number zzz, where the z=2z=2z=2 case corresponds to the one-dimensional (1D) scheme. For this ansatz, the long-range correlation deviates from the mean-field value polynomially with distance, in contrast to the matrix-product ansatz, which deviates exponentially. The computational cost of the tree-tensor-network method is significantly smaller than that of previous DMRG-based attempts, which renormalize several blocks into a single block. In addition, we investigate the effect of unitary transformations on the local basis states and present a method for optimizing such transformations. For the 1D interacting spinless fermion model, the optimized transformation interpolates smoothly between real space and momentum space. Calculations carried out on small quantum chemical systems support our approach.