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:cond-mat/0103146 · Physical Review Letters

Worm Algorithms for Classical Statistical Models

Nikolay V. Prokof'ev, Boris V. Svistunov

Published Sep 27, 2001• 387 citations
arXivHTMLPDF

Abstract

We show that high-temperature expansions provide a basis for the novel approach to efficient Monte Carlo simulations. "Worm" algorithms utilize the idea of updating closed-path configurations (produced by high-temperature expansions) through the motion of end points of a disconnected path. An amazing result is that local, Metropolis-type schemes using this approach appear to have dynamical critical exponents close to zero (i.e., their efficiency is comparable to the best cluster methods) as proved by finite-size scaling of the autocorrelation time for various universality classes.

DOI
10.1103/physrevlett.87.160601

Related papers

Worm Algorithm for Problems of Quantum and Classical Statistics

Nikolay V. Prokof'ev

Theoretical studies often involve mappings of the original system onto an equivalent description in terms of abstract mathematical/graphical objects, where ‘equivalent’ means one obtains the same final answer for some particular property. Path integrals, high-temperature expansions, and Feynman diagrams are the well-known examples considered in this chapter. Under such mappings, one has to deal with the infinite-dimensional configuration space having complex topology and non-local constraints which severely reduce efficiency of Monte Carlo simulations based on standard local updates. This sometimes leads to ergodicity problems in large systems when the entire configuration space can not be sampled in a reasonable computation time. A somewhat related difficulty facing conventional Monte Carlo schemes is the computation of off-diagonal correlation functions since they have no direct relation to the configuration space of the partition function. In what follows we consider path integrals for lattice and continuous systems, high-temperature expansions, and Feynman diagrams, explain the general idea of how Worm Algorithms (WAs) deal with the topological constraints by going to the enlarged configuration space, and present illustrative results for several physics problems.

arXiv:0910.1393•CRC Press eBooks•Nov 2, 2010•27 citations

Measuring the efficiency of the Worm algorithm and the Metropolis algorithm in producing statistically independent observations

Lauri A. Lehtimäki

In lattice field theories the partition function is often a very high dimensional integral which can’t be written in a closed form. In order to study the behaviour of the system one needs an efficient algorithm to approximate the high dimensional integral. In this thesis two Markov chain Monte Carlo algorithms the Metropolis algorithm and the Worm algorithm are used to simulate the three dimensional xy-model near its critical point. As the critical point is approached from below in terms of the inverse coupling the correlation length of the system diverges which may lead to the critical slowing down. An efficient algorithm is such that it suffers from the critical slowing down as little as possible which corresponds to a small dynamical critical exponent value. The efficiency of the algorithms is compared by measuring the integrated autocorrelation time of energy for different lattice sizes. The dynamical critical exponent, which controls the computational cost of the simulation, is calculated as a linear least squares fit to the integrated autocorrelation time data. From the simulated data the measured value of the dynamical critical exponent for the Metropolis algorithm is 1.85 and for the Worm algorithm the value is 0.37.

Työväentutkimus Vuosikirja•Jan 1, 2018•0 citations

Geometric allocation approach to accelerating directed worm algorithm

Hidemaro Suwa

The worm algorithm is a versatile technique in the Markov chain Monte Carlo method for both classical and quantum systems. The algorithm substantially alleviates critical slowing down and reduces the dynamic critical exponents of various classical systems. It is crucial to improve the algorithm and push the boundary of the Monte Carlo method for physical systems. We here propose a directed worm algorithm that significantly improves computational efficiency. We use the geometric allocation approach to optimize the worm scattering process: worm backscattering is averted, and forward scattering is favored. Our approach successfully enhances the diffusivity of the worm head (kink), which is evident in the probability distribution of the relative position of the two kinks. Performance improvement is demonstrated for the Ising model at the critical temperature by measurement of exponential autocorrelation times and asymptotic variances. The present worm update is approximately 25 times as efficient as the conventional worm update for the simple cubic lattice model. Surprisingly, our algorithm is even more efficient than the Wolff cluster algorithm, which is one of the best update algorithms. We estimate the dynamic critical exponent of the simple cubic lattice Ising model to be z≈0.27 in the worm update. The worm and the Wolff algorithms produce different exponents of the integrated autocorrelation time of the magnetic susceptibility estimator but the same exponent of the asymptotic variance. We also discuss how to quantify the computational efficiency of the Markov chain Monte Carlo method. Our approach can be applied to a wide range of physical systems, such as the |ϕ|^{4} model, the Potts model, the O(n) loop model, and lattice QCD.

arXiv:1703.03136•Physical review. E•Jan 13, 2021•8 citations

Dynamic Critical Behavior of the Worm Algorithm for the Ising Model

Youjin Deng, Timothy M. Garoni, Alan D. Sokal

We study the dynamic critical behavior of the worm algorithm for the two- and three-dimensional Ising models, by Monte Carlo simulation. The autocorrelation functions exhibit an unusual three-time-scale behavior. As a practical matter, the worm algorithm is slightly more efficient than the Swendsen-Wang algorithm for simulating the two-point function of the three-dimensional Ising model.

arXiv:cond-mat/0703787•Physical Review Letters•Sep 10, 2007•46 citations

Path integral Monte Carlo

V. Apaja

Using imaginary time, quantum statistical mechanics of a finite-temperature system in thermodynamical equilibrium turns into a problem of classical ring polymers made of particle paths. We need to consider all possible ring polymers at a given temperature, which again is where Monte Carlo methods are effective, especially using a so-called worm algorithm. We show how paths can be sampled using Monte Carlo, and how the physical properties, such as energy and radial distribution, are computed from the paths. Identical particles can have their paths exchanged at will, and we see how boson superfluidity comes out of this picture. Finally, the stochastic series expansion method is introduced to show finite temperature Hubbard model can be simulated.

Institute of Physics eBooks•Aug 1, 2025•0 citations

Temperature scaling in nonequilibrium relaxation in three-dimensional Heisenberg model in the Swendsen-Wang and Metropolis algorithms

Yoshihiko Nonomura, Yusuke Tomita

Recently the present authors proposed the nonequilibrium-to-equilibrium scaling (NE-ES) scheme for the critical Monte Carlo relaxation process [Nonomura, J. Phys. Soc. Jpn. 83, 113001 (2014)10.7566/JPSJ.83.113001], which scales relaxation data in the whole simulation-time regions regardless of functional forms, namely, both for the stretched-exponential critical relaxation in cluster algorithms and for the power-law critical relaxation in local-update algorithms. In the present study, we generalize this scheme to off-critical relaxation process and scale relaxation data for various temperatures in the whole simulation-time regions. This proposal of the off-critical scaling in cluster algorithms cannot be described by the dynamical finite-size scaling theory based on the power-law critical relaxation. As an example, we investigate the three-dimensional classical Heisenberg model previously analyzed with the NE-ES [Nonomura and Tomita, Phys. Rev. E 93, 012101 (2016)10.1103/PhysRevE.93.012101] in the Swendsen-Wang and Metropolis algorithms.

arXiv:2007.14356•Physical review. E•Nov 17, 2020•0 citations
We show that high-temperature expansions provide a basis for the novel approach to efficient Monte Carlo simulations. "Worm" algorithms utilize the idea of updating closed-path configurations (produced by high-temperature expansions) through the motion of end points of a disconnected path. An amazing result is that local, Metropolis-type schemes using this approach appear to have dynamical critical exponents close to zero (i.e., their efficiency is comparable to the best cluster methods) as proved by finite-size scaling of the autocorrelation time for various universality classes.
Theoretical studies often involve mappings of the original system onto an equivalent description in terms of abstract mathematical/graphical objects, where ‘equivalent’ means one obtains the same final answer for some particular property. Path integrals, high-temperature expansions, and Feynman diagrams are the well-known examples considered in this chapter. Under such mappings, one has to deal with the infinite-dimensional configuration space having complex topology and non-local constraints which severely reduce efficiency of Monte Carlo simulations based on standard local updates. This sometimes leads to ergodicity problems in large systems when the entire configuration space can not be sampled in a reasonable computation time. A somewhat related difficulty facing conventional Monte Carlo schemes is the computation of off-diagonal correlation functions since they have no direct relation to the configuration space of the partition function. In what follows we consider path integrals for lattice and continuous systems, high-temperature expansions, and Feynman diagrams, explain the general idea of how Worm Algorithms (WAs) deal with the topological constraints by going to the enlarged configuration space, and present illustrative results for several physics problems.
In lattice field theories the partition function is often a very high dimensional integral which can’t be written in a closed form. In order to study the behaviour of the system one needs an efficient algorithm to approximate the high dimensional integral. In this thesis two Markov chain Monte Carlo algorithms the Metropolis algorithm and the Worm algorithm are used to simulate the three dimensional xy-model near its critical point. As the critical point is approached from below in terms of the inverse coupling the correlation length of the system diverges which may lead to the critical slowing down. An efficient algorithm is such that it suffers from the critical slowing down as little as possible which corresponds to a small dynamical critical exponent value. The efficiency of the algorithms is compared by measuring the integrated autocorrelation time of energy for different lattice sizes. The dynamical critical exponent, which controls the computational cost of the simulation, is calculated as a linear least squares fit to the integrated autocorrelation time data. From the simulated data the measured value of the dynamical critical exponent for the Metropolis algorithm is 1.85 and for the Worm algorithm the value is 0.37.
The worm algorithm is a versatile technique in the Markov chain Monte Carlo method for both classical and quantum systems. The algorithm substantially alleviates critical slowing down and reduces the dynamic critical exponents of various classical systems. It is crucial to improve the algorithm and push the boundary of the Monte Carlo method for physical systems. We here propose a directed worm algorithm that significantly improves computational efficiency. We use the geometric allocation approach to optimize the worm scattering process: worm backscattering is averted, and forward scattering is favored. Our approach successfully enhances the diffusivity of the worm head (kink), which is evident in the probability distribution of the relative position of the two kinks. Performance improvement is demonstrated for the Ising model at the critical temperature by measurement of exponential autocorrelation times and asymptotic variances. The present worm update is approximately 25 times as efficient as the conventional worm update for the simple cubic lattice model. Surprisingly, our algorithm is even more efficient than the Wolff cluster algorithm, which is one of the best update algorithms. We estimate the dynamic critical exponent of the simple cubic lattice Ising model to be z≈0.27 in the worm update. The worm and the Wolff algorithms produce different exponents of the integrated autocorrelation time of the magnetic susceptibility estimator but the same exponent of the asymptotic variance. We also discuss how to quantify the computational efficiency of the Markov chain Monte Carlo method. Our approach can be applied to a wide range of physical systems, such as the |ϕ|^{4} model, the Potts model, the O(n) loop model, and lattice QCD.
Using imaginary time, quantum statistical mechanics of a finite-temperature system in thermodynamical equilibrium turns into a problem of classical ring polymers made of particle paths. We need to consider all possible ring polymers at a given temperature, which again is where Monte Carlo methods are effective, especially using a so-called worm algorithm. We show how paths can be sampled using Monte Carlo, and how the physical properties, such as energy and radial distribution, are computed from the paths. Identical particles can have their paths exchanged at will, and we see how boson superfluidity comes out of this picture. Finally, the stochastic series expansion method is introduced to show finite temperature Hubbard model can be simulated.
Recently the present authors proposed the nonequilibrium-to-equilibrium scaling (NE-ES) scheme for the critical Monte Carlo relaxation process [Nonomura, J. Phys. Soc. Jpn. 83, 113001 (2014)10.7566/JPSJ.83.113001], which scales relaxation data in the whole simulation-time regions regardless of functional forms, namely, both for the stretched-exponential critical relaxation in cluster algorithms and for the power-law critical relaxation in local-update algorithms. In the present study, we generalize this scheme to off-critical relaxation process and scale relaxation data for various temperatures in the whole simulation-time regions. This proposal of the off-critical scaling in cluster algorithms cannot be described by the dynamical finite-size scaling theory based on the power-law critical relaxation. As an example, we investigate the three-dimensional classical Heisenberg model previously analyzed with the NE-ES [Nonomura and Tomita, Phys. Rev. E 93, 012101 (2016)10.1103/PhysRevE.93.012101] in the Swendsen-Wang and Metropolis algorithms.