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

Markov Chain Monte Carlo without Detailed Balance

Hidemaro Suwa, Synge Todo

Published Jul 14, 2010• 0 citations
OpenAlex

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.

Related papers

Markov Chain Monte Carlo Method 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.

arXiv:1007.2262•Physical Review Letters•Sep 17, 2010•148 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

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

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

Many-Configuration Markov-Chain Monte Carlo

Fedor Šimkovic, Riccardo Rossi

We propose a minimal generalization of the celebrated Markov-Chain Monte Carlo algorithm which allows for an arbitrary number of configurations to be visited at every Monte Carlo step. This is advantageous when a parallel computing machine is available, or when many biased configurations can be evaluated at little additional computational cost. As an example of the former case, we report a significant reduction of the thermalization time for the paradigmatic Sherrington-Kirkpatrick spin-glass model. For the latter case, we show that, by leveraging on the exponential number of biased configurations automatically computed by Diagrammatic Monte Carlo, we can speed up computations in the Fermi-Hubbard model by two orders of magnitude.

arXiv:2102.05613•Feb 10, 2021•5 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 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 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.
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 propose a minimal generalization of the celebrated Markov-Chain Monte Carlo algorithm which allows for an arbitrary number of configurations to be visited at every Monte Carlo step. This is advantageous when a parallel computing machine is available, or when many biased configurations can be evaluated at little additional computational cost. As an example of the former case, we report a significant reduction of the thermalization time for the paradigmatic Sherrington-Kirkpatrick spin-glass model. For the latter case, we show that, by leveraging on the exponential number of biased configurations automatically computed by Diagrammatic Monte Carlo, we can speed up computations in the Fermi-Hubbard model by two orders of magnitude.
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.