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:1007.2262 · Physical Review Letters

Markov Chain Monte Carlo Method without Detailed Balance

Hidemaro Suwa, Synge Todo

Published Sep 17, 2010• 148 citations
arXivHTMLPDF

Abstract

We present a specific algorithm that generally satisfies the balance condition without imposing the detailed balance in the Markov chain Monte Carlo. In our algorithm, the average rejection rate is minimized, and even reduced to zero in many relevant cases. The absence of the detailed balance also introduces a net stochastic flow in a configuration space, which further boosts up the convergence. We demonstrate that the autocorrelation time of the Potts model becomes more than 6 times shorter than that by the conventional Metropolis algorithm. Based on the same concept, a bounce-free worm algorithm for generic quantum spin models is formulated as well.

DOI
10.1103/physrevlett.105.120603

Related papers

Markov Chain Monte Carlo without Detailed Balance

Hidemaro Suwa, Synge Todo

We present a specific algorithm that generally satisfies the balance condition without imposing the detailed balance in the Markov chain Monte Carlo. In our algorithm, the average rejection rate is minimized, and even reduced to zero in many relevant cases. The absence of the detailed balance also introduces a net stochastic flow in a configuration space, which further boosts up the convergence. We demonstrate that the autocorrelation time of the Potts model becomes more than 6 times shorter than that by the conventional Metropolis algorithm. Based on the same concept, a bounce-free worm algorithm for generic quantum spin models is formulated as well.

•Jul 14, 2010•0 citations

Quantum Monte Carlo algorithm for arbitrary spin-1/2 Hamiltonians

Lev Barash, Arman Babakhani, Itay Hen

We present a universal parameter-free quantum Monte Carlo (QMC) algorithm designed to simulate arbitrary spin- 1/2 Hamiltonians. To ensure the convergence of the Markov chain to equilibrium for every conceivable case, we devise a clear and simple automated protocol that produces QMC updates that are provably ergodic and satisfy detailed balance. We demonstrate the applicability and versatility of our method by considering several illustrative examples, including the simulation of the XY model on a triangular lattice, the toric code, and random k -local Hamiltonians. Published by the American Physical Society 2024

arXiv:2307.06503•Physical Review Research•Mar 14, 2024•5 citations

A method to reduce the rejection rate in Monte Carlo Markov Chains on Ising spin models

Carlo Baldassi

We present a method for Monte Carlo sampling on Ising spin systems, introducing a prior on the candidate moves in a Metropolis-Hastings scheme which can significantly reduce the rejection rate. The method can be regarded as an modification of the rejection-free method of Bortz, Kalos and Lebowitz (BKL) [Bortz et al. 1975], which was developed under two assumptions: i) low connectivity, and ii) that the energy shift induced by flipping one spin can only assume a small number of values. Our method employs the same probability distribution for the choice of the moves as BKL, but uses it as a prior in an otherwise standard Metropolis scheme: it is thus not fully rejection-free, but in a wide range of scenarios it is nearly so; moreover, it is easily extensible to more general situations which cannot be treated with the BKL method, in particular when the energy of the system can be written as the sum of two components, only one of which satisfies the assumptions at the basis of the BKL method. We provide two families of examples of such situations: graphs with heterogeneous continuous-valued couplings, and Monte Carlo simulations of quantum spin models in presence of a transverse field in the Suzuki-Trotter formalism. Our code is publicly available [this https URL], and extensible to user-defined models.

arXiv:1608.05899•Aug 21, 2016•1 citation

A Hybrid Method for Global Updates in Monte Carlo Study

Tomo Munehisa, Yasuko Munehisa

We propose a new algorithm which works effectively in global updates in Monte Carlo study. We apply it to the quantum spin chain with next-nearest-neighbor interactions. We observe that Monte Carlo results are in excellent agreement with numerically exact ones obtained by the transfer matrix method. 1 The Monte Carlo method has been an indispensable tool for theoretial study in physics. An essential point of the method is to generate configurations according to their Boltzmann weights. For this purpose one usually starts with an initial configuration and obtains a new configuration sequantially by some rule that guarantees the ergodicity and satisfies the condition of the detailed balance. Widely used rules are the heat bath method and the Metropolis algorithm. The heat bath mehtod is useful for systems which have a small number of candidates for updating because one has to calculate weights for all candidates to determine which one should make the new configuration. The Metropolis algorithm is suitable for complicated systems since in this algorithm it is enough to know the weight just for one candidate

•Jan 1, 1994•1 citation

Event-chain algorithm for the Heisenberg model: Evidence for z≃1 dynamic scaling

Yoshihiko Nishikawa, Manon Michel, Werner Krauth +1 more

We apply the event-chain Monte Carlo algorithm to the three-dimensional ferromagnetic Heisenberg model. The algorithm is rejection-free and also realizes an irreversible Markov chain that satisfies global balance. The autocorrelation functions of the magnetic susceptibility and the energy indicate a dynamical critical exponent z≈1 at the critical temperature, while that of the magnetization does not measure the performance of the algorithm. We show that the event-chain Monte Carlo algorithm substantially reduces the dynamical critical exponent from the conventional value of z≃2.

arXiv:1508.05661•Physical Review E•Dec 14, 2015•42 citations

Generalized directed loop method for quantum Monte Carlo simulations

Fabien Alet, Stefan Weßel, Matthias Troyer

Efficient quantum Monte Carlo update schemes called directed loops have recently been proposed, which improve the efficiency of simulations of quantum lattice models. We propose to generalize the detailed balance equations at the local level during the loop construction by accounting for the matrix elements of the operators associated with open world-line segments. Using linear programming techniques to solve the generalized equations, we look for optimal construction schemes for directed loops. This also allows for an extension of the directed loop scheme to general lattice models, such as high-spin or bosonic models. The resulting algorithms are bounce free in larger regions of parameter space than the original directed loop algorithm. The generalized directed loop method is applied to the magnetization process of spin chains in order to compare its efficiency to that of previous directed loop schemes. In contrast to general expectations, we find that minimizing bounces alone does not always lead to more efficient algorithms in terms of autocorrelations of physical observables, because of the nonuniqueness of the bounce-free solutions. We therefore propose different general strategies to further minimize autocorrelations, which can be used as supplementary requirements in any directed loop scheme. We show by calculating autocorrelation times for different observables that such strategies indeed lead to improved efficiency; however, we find that the optimal strategy depends not only on the model parameters but also on the observable of interest.

arXiv:cond-mat/0308495•Physical Review E•Mar 22, 2005•244 citations
We present a specific algorithm that generally satisfies the balance condition without imposing the detailed balance in the Markov chain Monte Carlo. In our algorithm, the average rejection rate is minimized, and even reduced to zero in many relevant cases. The absence of the detailed balance also introduces a net stochastic flow in a configuration space, which further boosts up the convergence. We demonstrate that the autocorrelation time of the Potts model becomes more than 6 times shorter than that by the conventional Metropolis algorithm. Based on the same concept, a bounce-free worm algorithm for generic quantum spin models is formulated as well.
We present a specific algorithm that generally satisfies the balance condition without imposing the detailed balance in the Markov chain Monte Carlo. In our algorithm, the average rejection rate is minimized, and even reduced to zero in many relevant cases. The absence of the detailed balance also introduces a net stochastic flow in a configuration space, which further boosts up the convergence. We demonstrate that the autocorrelation time of the Potts model becomes more than 6 times shorter than that by the conventional Metropolis algorithm. Based on the same concept, a bounce-free worm algorithm for generic quantum spin models is formulated as well.
We present a universal parameter-free quantum Monte Carlo (QMC) algorithm designed to simulate arbitrary spin- 1/2 Hamiltonians. To ensure the convergence of the Markov chain to equilibrium for every conceivable case, we devise a clear and simple automated protocol that produces QMC updates that are provably ergodic and satisfy detailed balance. We demonstrate the applicability and versatility of our method by considering several illustrative examples, including the simulation of the XY model on a triangular lattice, the toric code, and random k -local Hamiltonians. Published by the American Physical Society 2024
We present a method for Monte Carlo sampling on Ising spin systems, introducing a prior on the candidate moves in a Metropolis-Hastings scheme which can significantly reduce the rejection rate. The method can be regarded as an modification of the rejection-free method of Bortz, Kalos and Lebowitz (BKL) [Bortz et al. 1975], which was developed under two assumptions: i) low connectivity, and ii) that the energy shift induced by flipping one spin can only assume a small number of values. Our method employs the same probability distribution for the choice of the moves as BKL, but uses it as a prior in an otherwise standard Metropolis scheme: it is thus not fully rejection-free, but in a wide range of scenarios it is nearly so; moreover, it is easily extensible to more general situations which cannot be treated with the BKL method, in particular when the energy of the system can be written as the sum of two components, only one of which satisfies the assumptions at the basis of the BKL method. We provide two families of examples of such situations: graphs with heterogeneous continuous-valued couplings, and Monte Carlo simulations of quantum spin models in presence of a transverse field in the Suzuki-Trotter formalism. Our code is publicly available [this https URL], and extensible to user-defined models.
We propose a new algorithm which works effectively in global updates in Monte Carlo study. We apply it to the quantum spin chain with next-nearest-neighbor interactions. We observe that Monte Carlo results are in excellent agreement with numerically exact ones obtained by the transfer matrix method. 1 The Monte Carlo method has been an indispensable tool for theoretial study in physics. An essential point of the method is to generate configurations according to their Boltzmann weights. For this purpose one usually starts with an initial configuration and obtains a new configuration sequantially by some rule that guarantees the ergodicity and satisfies the condition of the detailed balance. Widely used rules are the heat bath method and the Metropolis algorithm. The heat bath mehtod is useful for systems which have a small number of candidates for updating because one has to calculate weights for all candidates to determine which one should make the new configuration. The Metropolis algorithm is suitable for complicated systems since in this algorithm it is enough to know the weight just for one candidate
We apply the event-chain Monte Carlo algorithm to the three-dimensional ferromagnetic Heisenberg model. The algorithm is rejection-free and also realizes an irreversible Markov chain that satisfies global balance. The autocorrelation functions of the magnetic susceptibility and the energy indicate a dynamical critical exponent z≈1 at the critical temperature, while that of the magnetization does not measure the performance of the algorithm. We show that the event-chain Monte Carlo algorithm substantially reduces the dynamical critical exponent from the conventional value of z≃2.
Efficient quantum Monte Carlo update schemes called directed loops have recently been proposed, which improve the efficiency of simulations of quantum lattice models. We propose to generalize the detailed balance equations at the local level during the loop construction by accounting for the matrix elements of the operators associated with open world-line segments. Using linear programming techniques to solve the generalized equations, we look for optimal construction schemes for directed loops. This also allows for an extension of the directed loop scheme to general lattice models, such as high-spin or bosonic models. The resulting algorithms are bounce free in larger regions of parameter space than the original directed loop algorithm. The generalized directed loop method is applied to the magnetization process of spin chains in order to compare its efficiency to that of previous directed loop schemes. In contrast to general expectations, we find that minimizing bounces alone does not always lead to more efficient algorithms in terms of autocorrelations of physical observables, because of the nonuniqueness of the bounce-free solutions. We therefore propose different general strategies to further minimize autocorrelations, which can be used as supplementary requirements in any directed loop scheme. We show by calculating autocorrelation times for different observables that such strategies indeed lead to improved efficiency; however, we find that the optimal strategy depends not only on the model parameters but also on the observable of interest.