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

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

Stefano Crotti

Published Jan 17, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.13121/polito/porto/2996778

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

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

Statistical mechanics of disordered quantum optimization

Chris R. Laumann

The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.

•Jan 1, 2010•1 citation

Computational studies of thermal and quantum phase transitions approached through non-equilibrium quenching

Chengwei Liu

Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.

•Jan 1, 2015•0 citations

Nonequilibrium Dynamics of Strongly Correlated Systems

Joseph Kleinhenz

In this thesis, we describe methods for solving quantum impurity models out of equilibrium, and consider several applications of these methods. Quantum impurity models describe systems in which a small subsystem (the impurity) is coupled to a large external environment (the bath). These models are useful in describing a wide variety of physical systems, including quantum dots, absorbed adatoms, and molecular junctions. They are also important for the study of lattice models, such as the Hubbard model, where they appear as auxiliary problems within the framework of dynamical mean field theory (DMFT). Many interesting phenomena in these systems, such as transport through a quantum dot, or optical pumping of a Mott insulator, occur away from equilibrium. Theoretical description of these phenomena requires methods that are capable of handling both real time evolution and strong correlation effects presenting a formidable challenge. In this thesis, we describe several methods for the solution of non-equilibrium quantum impurity models which meet this challenge. These methods are based on an expansion in the coupling between the impurity and the bath known as the hybridization expansion. Chapter 1 gives an introduction to the problems addressed in this thesis. Chapter 2 provides a brief overview of Keldysh formalism for nonequilibrium problems. Chapter 3 describes the bare hybridization expansion for the Anderson impurity model as well as its bold extensions. In particular we derive the non-crossing approximation (NCA), the one-crossing approximation (OCA), the inchworm expansion, and a bold expansion for the impurity Green's function. Chapter 4 describes the implementation of a quantum Monte Carlo algorithm based on the inchworm expansion. The rest of the thesis describes applications of these algorithms to problems of physical interest. Chapters 5 and 6 apply the methods previously described to understanding the Kondo effect in quantum dot systems. The first chapter examines the behavior of the Kondo effect under an applied voltage bias, a classic non-equilibrium strongly-correlated problem. The second chapter examines different ways of measuring the cloud of electrons which screen the impurity spin in the Kondo regime. Chapters 7 and 8 apply the same methods to the Hubbard model using the Dynamical mean-field theory (DMFT) mapping. The first chapter studies the Hubbard model in equilibrium using the numerically exact inchworm quantum Monte Carlo method. The second chapter studies the possibility of dynamic switching between the metal and Mott-insulator states of the Hubbard model using the one-crossing approximation (OCA). Finally chapter 9 gives some overall conclusions and suggests future directions for the development of hybridization expansion methods.

•Jan 1, 2021•1 citation
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 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 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.
The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.
Phase transitions and their associated critical phenomena are of fundamental importance and play a crucial role in the development of statistical physics for both classical and quantum systems. Phase transitions embody diverse aspects of physics and also have numerous applications outside physics, e.g., in chemistry, biology, and combinatorial optimization problems in computer science. Many problems can be reduced to a system consisting of a large number of interacting agents, which under some circumstances (e.g., changes of external parameters) exhibit collective behavior; this type of scenario also underlies phase transitions. The theoretical understanding of equilibrium phase transitions was put on a solid footing with the establishment of the renormalization group. In contrast, non-equilibrium phase transition are relatively less understood and currently a very active research topic. One important milestone here is the Kibble-Zurek (KZ) mechanism, which provides a useful framework for describing a system with a transition point approached through a non-equilibrium quench process. I developed two efficient Monte Carlo techniques for studying phase transitions, one is for classical phase transition and the other is for quantum phase transitions, both are under the framework of KZ scaling. For classical phase transition, I develop a non-equilibrium quench (NEQ) simulation that can completely avoid the critical slowing down problem. For quantum phase transitions, I develop a new algorithm, named quasi-adiabatic quantum Monte Carlo (QAQMC) algorithm for studying quantum quenches. I demonstrate the utility of QAQMC quantum Ising model and obtain high-precision results at the transition point, in particular showing generalized dynamic scaling in the quantum system. To further extend the methods, I study more complex systems such as spin-glasses and random graphs. The techniques allow us to investigate the problems efficiently. From the classical perspective, using the NEQ approach I verify the universality class of the 3D Ising spin-glasses. I also investigate the random 3-regular graphs in terms of both classical and quantum phase transitions. I demonstrate that under this simulation scheme, one can extract information associated with the classical and quantum spin-glass transitions without any knowledge prior to the simulation.
In this thesis, we describe methods for solving quantum impurity models out of equilibrium, and consider several applications of these methods. Quantum impurity models describe systems in which a small subsystem (the impurity) is coupled to a large external environment (the bath). These models are useful in describing a wide variety of physical systems, including quantum dots, absorbed adatoms, and molecular junctions. They are also important for the study of lattice models, such as the Hubbard model, where they appear as auxiliary problems within the framework of dynamical mean field theory (DMFT). Many interesting phenomena in these systems, such as transport through a quantum dot, or optical pumping of a Mott insulator, occur away from equilibrium. Theoretical description of these phenomena requires methods that are capable of handling both real time evolution and strong correlation effects presenting a formidable challenge. In this thesis, we describe several methods for the solution of non-equilibrium quantum impurity models which meet this challenge. These methods are based on an expansion in the coupling between the impurity and the bath known as the hybridization expansion. Chapter 1 gives an introduction to the problems addressed in this thesis. Chapter 2 provides a brief overview of Keldysh formalism for nonequilibrium problems. Chapter 3 describes the bare hybridization expansion for the Anderson impurity model as well as its bold extensions. In particular we derive the non-crossing approximation (NCA), the one-crossing approximation (OCA), the inchworm expansion, and a bold expansion for the impurity Green's function. Chapter 4 describes the implementation of a quantum Monte Carlo algorithm based on the inchworm expansion. The rest of the thesis describes applications of these algorithms to problems of physical interest. Chapters 5 and 6 apply the methods previously described to understanding the Kondo effect in quantum dot systems. The first chapter examines the behavior of the Kondo effect under an applied voltage bias, a classic non-equilibrium strongly-correlated problem. The second chapter examines different ways of measuring the cloud of electrons which screen the impurity spin in the Kondo regime. Chapters 7 and 8 apply the same methods to the Hubbard model using the Dynamical mean-field theory (DMFT) mapping. The first chapter studies the Hubbard model in equilibrium using the numerically exact inchworm quantum Monte Carlo method. The second chapter studies the possibility of dynamic switching between the metal and Mott-insulator states of the Hubbard model using the one-crossing approximation (OCA). Finally chapter 9 gives some overall conclusions and suggests future directions for the development of hybridization expansion methods.