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$ .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.03893Oct 6, 20260 citations

Cluster Monte Carlo and dynamical scaling for long-range interactions

Emilio Flores-Sola, Martin Weigel, Ralph Kenna B +1 more

arXiv:1611.05659The European Physical Journal Special TopicsApr 1, 201715 citations

Extending Monte Carlo samples

Bernard B. Beard

Nuclear Physics B - Proceedings SupplementsMay 1, 20031 citation

The Development of Cluster and Histogram Methods

Robert H. Swendsen

This talk will review the history of both cluster and histogram methods for Monte Carlo simulations. Cluster methods are based on the famous exact mapping by Fortuin and Kasteleyn from general Potts models onto a percolation representation. I will discuss the Swendsen‐Wang algorithm, as well as its improvement and extension to more general spin models by Wolff. The Replica Monte Carlo method further extended cluster simulations to deal with frustrated systems. The history of histograms is quite extensive, and can only be summarized briefly in this talk. It goes back at least to work by Salsburg et al. in 1959. Since then, it has been forgotten and rediscovered several times. The modern use of the method has exploited its ability to efficiently determine the location and height of peaks in various quantities, which is of prime importance in the analysis of critical phenomena. The extensions of this approach to the multiple histogram method and multicanonical ensembles have allowed information to be obtained over a broad range of parameters. Histogram simulations and analyses have become standard techniques in Monte Carlo simulations.This talk will review the history of both cluster and histogram methods for Monte Carlo simulations. Cluster methods are based on the famous exact mapping by Fortuin and Kasteleyn from general Potts models onto a percolation representation. I will discuss the Swendsen‐Wang algorithm, as well as its improvement and extension to more general spin models by Wolff. The Replica Monte Carlo method further extended cluster simulations to deal with frustrated systems. The history of histograms is quite extensive, and can only be summarized briefly in this talk. It goes back at least to work by Salsburg et al. in 1959. Since then, it has been forgotten and rediscovered several times. The modern use of the method has exploited its ability to efficiently determine the location and height of peaks in various quantities, which is of prime importance in the analysis of critical phenomena. The extensions of this approach to the multiple histogram method and multicanonical ensembles have allowed information to be obtained over a broad range of parameters. Histogram simulations and analyses have become standard techniques in Monte Carlo simulations.

AIP conference proceedingsJan 1, 20030 citations

On the Power of Restricted Monte Carlo Algorithms

Stefan Heinrich

MATRIX book seriesJan 1, 20203 citations

Tuning the generalized Hybrid Monte Carlo algorithm

Anthony D. Kennedy, Robert G. Edwards, H. Mino +1 more

arXiv:hep-lat/9509043Nuclear Physics B - Proceedings SupplementsMar 1, 19968 citations

(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