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

Physical review. B, Condensed matter

Extended cluster algorithm in quantum simulations

Hiromi Otsuka

Published Jun 20, 2001• 1 citation
Publisher

Abstract

We propose an extension of the quantum cluster algorithm by a combined use of the Fortuin-Kasteleyn mapping and the Hubbard-Stratonovich transformation. To describe the idea, we consider the $S=\frac{1}{2}$ $\mathrm{XXZ}$ chain model and express the partition function as the sum in an extended configuration space of spins, graphs, and fields. Then it is clarified that this algorithm possesses a computationally tractable continuous-time limit and maintains virtues of the quantum cluster algorithm. Numerical simulations are performed and its applicability is demonstrated. Further, we discuss potential gains in our algorithm.

DOI
10.1103/physrevb.64.020406

Related papers

Cluster algorithm for Potts models with fixed spin densities

R. P. Bikker, G. T. Barkema

A cluster algorithm is presented for the simulation of the q-state Potts models in which the number of spins is conserved in each state. The algorithm constructs Fortuin-Kasteleyn cluster configurations from spin configurations, in a way identical to the Swendsen-Wang algorithm; the spin assignment to these clusters is, however, different, and conserves the number of spins for each state. Compared to traditional nonlocal spin-exchange algorithms, the cluster algorithm presented here suffers less from critical slowing down, and consequently is more efficient near the critical temperature.

arXiv:cond-mat/0005076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Oct 1, 2000•3 citations

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$, where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$. For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$, this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$, where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$, including $2$-local models with $α>2D$.

quant-pharXiv:2610.03893•Oct 6, 2026•0 citations

Cluster Algorithms for General- S Quantum Spin Systems

Synge Todo, Kiyoshi Katō

We present a general strategy to extend quantum cluster algorithms for $S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}$ spin systems, such as the loop algorithm, to those with an arbitrary size of spins. The partition function of a high- $S$ spin system is generally represented by the path integral of a $S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}$ model with special boundary conditions in the imaginary-time direction. We introduce additional graphs for the boundary part and give the labeling probability explicitly, which completes the algorithm together with an existing $S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}$ algorithm. As a demonstration, we simulate the integer-spin antiferromagnetic Heisenberg chains. The magnitude of the first excitation gap is estimated to be 0.41048(6), 0.08917(4), and 0.01002(3) for $S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}1$, 2, and 3, respectively.

arXiv:cond-mat/9911047•Physical Review Letters•Jul 6, 2001•270 citations

Cluster algorithms with empahsis on quantum spin systems

James E. Gubernatis, Naoki Kawashima

The purpose of this lecture is to discuss in detail the generalized approach of Kawashima and Gubernatis for the construction of cluster algorithms. We first present a brief refresher on the Monte Carlo method, describe the Swendsen-Wang algorithm, show how this algorithm follows from the Fortuin-Kastelyn transformation, and re=interpret this transformation in a form which is the basis of the generalized approach. We then derive the essential equations of the generalized approach. This derivation is remarkably simple if done from the viewpoint of probability theory, and the essential assumptions will be clearly stated. These assumptions are implicit in all useful cluster algorithms of which we are aware. They lead to a quite different perspective on cluster algorithms than found in the seminal works and in Ising model applications. Next, we illustrate how the generalized approach leads to a cluster algorithm for world-line quantum Monte Carlo simulations of Heisenberg models with S = 1/2. More succinctly, we also discuss the generalization of the Fortuin- Kasetelyn transformation to higher spin models and illustrate the essential steps for a S = 1 Heisenberg model. Finally, we summarize how to go beyond S = 1 to a general spin, XYZ model.

•Oct 6, 1995•0 citations

Efficient simulation of the random-cluster model

Eren Metin Elçi, Martin Weigel

The simulation of spin models close to critical points of continuous phase transitions is heavily impeded by the occurrence of critical slowing down. A number of cluster algorithms, usually based on the Fortuin-Kasteleyn representation of the Potts model, and suitable generalizations for continuous-spin models have been used to increase simulation efficiency. The first algorithm making use of this representation, suggested by Sweeny in 1983, has not found widespread adoption due to problems in its implementation. However, it has been recently shown that it is indeed more efficient in reducing critical slowing down than the more well-known algorithm due to Swendsen and Wang. Here, we present an efficient implementation of Sweeny's approach for the random-cluster model using recent algorithmic advances in dynamic connectivity algorithms.

arXiv:1307.6647•Physical Review E•Sep 16, 2013•17 citations

CLUSTER MONTE CARLO STUDY OF THE QUANTUM XY MODEL IN TWO DIMENSIONS

Naoki Kawashima, Mark Jarrell, James E. Gubernatis

The recent generalization of the Fortuin-Kasteleyn percolation representation and the Swendsen-Wang (SW) cluster algorithm is reviewed. The new representation yields cluster algorithm for the XYZ model with arbitrary magnitude of spins, with arbitrary anisotropies, and in any dimensions. The new algorithm often reduces computational autocorrelation times by several orders of magnitude. By using the new algorithm together with methods of Bayesian statistical inference, we obtained the dynamical structure factor S (k, ω) for the S =1/2 XY model in two dimensions.

International Journal of Modern Physics C•Jun 1, 1996•3 citations
We propose an extension of the quantum cluster algorithm by a combined use of the Fortuin-Kasteleyn mapping and the Hubbard-Stratonovich transformation. To describe the idea, we consider the S=12S=\frac{1}{2}S=21​ XXZ\mathrm{XXZ}XXZ chain model and express the partition function as the sum in an extended configuration space of spins, graphs, and fields. Then it is clarified that this algorithm possesses a computationally tractable continuous-time limit and maintains virtues of the quantum cluster algorithm. Numerical simulations are performed and its applicability is demonstrated. Further, we discuss potential gains in our algorithm.
A cluster algorithm is presented for the simulation of the q-state Potts models in which the number of spins is conserved in each state. The algorithm constructs Fortuin-Kasteleyn cluster configurations from spin configurations, in a way identical to the Swendsen-Wang algorithm; the spin assignment to these clusters is, however, different, and conserves the number of spins for each state. Compared to traditional nonlocal spin-exchange algorithms, the cluster algorithm presented here suffers less from critical slowing down, and consequently is more efficient near the critical temperature.
The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of (Nε−1)O(log⁡Δ)(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}(Nε−1)O(logΔ), where NNN is the system size, ε\varepsilonε the desired precision, and ΔΔΔ the interaction-graph degree. This becomes particularly severe in long-range systems, where Δ≡NΔ\equiv NΔ≡N, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime O~(N4ε−3)\tilde{\mathcal{O}}(N^4\varepsilon^{-3})O~(N4ε−3). For quantum partition functions at temperatures β≤βsampling≡O(1)β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)β≤βsampling​≡O(1), this improves to O~(N3+1/Dε−3)\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})O~(N3+1/Dε−3), where DDD is the lattice dimension. The framework directly applies to long-range quantum systems with interactions ∝1/rα\propto1/r^α∝1/rα, including 222-local models with α>2Dα>2Dα>2D.
We present a general strategy to extend quantum cluster algorithms for S=12S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}S=21​ spin systems, such as the loop algorithm, to those with an arbitrary size of spins. The partition function of a high- SSS spin system is generally represented by the path integral of a S=12S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}S=21​ model with special boundary conditions in the imaginary-time direction. We introduce additional graphs for the boundary part and give the labeling probability explicitly, which completes the algorithm together with an existing S=12S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}\frac{1}{2}S=21​ algorithm. As a demonstration, we simulate the integer-spin antiferromagnetic Heisenberg chains. The magnitude of the first excitation gap is estimated to be 0.41048(6), 0.08917(4), and 0.01002(3) for S=1S\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}1S=1, 2, and 3, respectively.
The purpose of this lecture is to discuss in detail the generalized approach of Kawashima and Gubernatis for the construction of cluster algorithms. We first present a brief refresher on the Monte Carlo method, describe the Swendsen-Wang algorithm, show how this algorithm follows from the Fortuin-Kastelyn transformation, and re=interpret this transformation in a form which is the basis of the generalized approach. We then derive the essential equations of the generalized approach. This derivation is remarkably simple if done from the viewpoint of probability theory, and the essential assumptions will be clearly stated. These assumptions are implicit in all useful cluster algorithms of which we are aware. They lead to a quite different perspective on cluster algorithms than found in the seminal works and in Ising model applications. Next, we illustrate how the generalized approach leads to a cluster algorithm for world-line quantum Monte Carlo simulations of Heisenberg models with S = 1/2. More succinctly, we also discuss the generalization of the Fortuin- Kasetelyn transformation to higher spin models and illustrate the essential steps for a S = 1 Heisenberg model. Finally, we summarize how to go beyond S = 1 to a general spin, XYZ model.
The simulation of spin models close to critical points of continuous phase transitions is heavily impeded by the occurrence of critical slowing down. A number of cluster algorithms, usually based on the Fortuin-Kasteleyn representation of the Potts model, and suitable generalizations for continuous-spin models have been used to increase simulation efficiency. The first algorithm making use of this representation, suggested by Sweeny in 1983, has not found widespread adoption due to problems in its implementation. However, it has been recently shown that it is indeed more efficient in reducing critical slowing down than the more well-known algorithm due to Swendsen and Wang. Here, we present an efficient implementation of Sweeny's approach for the random-cluster model using recent algorithmic advances in dynamic connectivity algorithms.
The recent generalization of the Fortuin-Kasteleyn percolation representation and the Swendsen-Wang (SW) cluster algorithm is reviewed. The new representation yields cluster algorithm for the XYZ model with arbitrary magnitude of spins, with arbitrary anisotropies, and in any dimensions. The new algorithm often reduces computational autocorrelation times by several orders of magnitude. By using the new algorithm together with methods of Bayesian statistical inference, we obtained the dynamical structure factor S (k, ω) for the S =1/2 XY model in two dimensions.