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:2610.03893

Efficient Quantum Monte Carlo through Cluster Expansions

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

quant-phcond-mat.stat-mechSubmitted Oct 2, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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$.

Related papers

State and superstate sampling in hybridization-expansion continuous-time quantum Monte Carlo

Alexander Kowalski, Andreas Hausoel, Markus Wallerberger +2 more

Due to the intrinsic complexity of the quantum many-body problem, quantum Monte Carlo algorithms and their corresponding Monte Carlo configurations can be defined in various ways. Configurations corresponding to few Feynman diagrams often lead to severe sign problems. On the other hand, computing the configuration weight becomes numerically expensive in the opposite limit in which many diagrams are grouped together. Here we show that for continuous-time quantum Monte Carlo in the hybridization expansion the efficiency can be substantially improved by dividing the local impurity trace into fragments, which are then sampled individually. For this technique, which also turns out to preserve the fermionic sign, a modified update strategy is introduced in order to ensure ergodicity. Our (super)state sampling is particularly beneficial to calculations with many $d$ orbitals and general local interactions, such as full Coulomb interaction. For illustration, we reconsider the simple albeit well-known case of a degenerate three-orbital model at low temperatures. This allows us to quantify the coherence properties of the ``spin-freezing'' crossover, even close to the Mott transition.

arXiv:1807.00361•Physical review. B./Physical review. B•Apr 8, 2019•24 citations

Exact and fast series expansions for quantum models with long-range interactions

Antonia Duft, Patrick Adelhardt, Jan Alexander Koziol +2 more

Over the past decade, high-order series expansions based on linked-cluster methods have become an important tool for studying low-energy properties of gapped quantum systems with long-range interactions. We introduce a deterministic framework that removes a central computational bottleneck of this method. Our graph zeta method replaces the costly and statistically noisy Monte Carlo (MC) evaluation of high-dimensional lattice sums by a systematic, high-precision computation that delivers series coefficients within minutes on standard desktop hardware. The full momentum-dependent series is obtained in a single calculation, enabling high-resolution excitation spectra throughout the Brillouin zone. Building on the companion paper [1], the method reformulates graph-embedding sums as graph zeta functions and decomposes them into blocks classified by their treewidth tw. Low-treewidth blocks (tw$\leq2$) admit closed expressions based on Epstein zeta functions, while higher-treewidth blocks (tw$>2$) are evaluated using tensor-network bucket elimination. We benchmark the approach for transverse-field Ising models with power-law interactions in 1d, 2d, and 3d, reproducing previous MC results at a fraction of the computational cost while enabling substantially denser parameter sampling. An open-source implementation makes the method directly applicable to general interactions and large parameter scans. As an application, we compare microscopic interaction models for the stacked quasi-2d transverse-field Ising triangular-lattice antiferromagnet KTmSe$_2$ and find that a model including dipolar interactions best describes existing experimental data. The graph zeta method thus turns high-order linked-cluster expansions into a practical and deterministic tool for fast quantitative momentum-resolved modeling of short- and long-range quantum matter.

cond-mat.str-elCross-listedarXiv:2609.18761•Sep 17, 2026•0 citations

Graph lattice sums and graph zeta functions for long-range interacting quantum lattice models

Andreas Alexander Buchheit, Andreas Rupp

Taming the exponential increase of the Hilbert space dimension with system size in the simulation of gapped quantum lattice models is of the highest relevance for understanding and designing exotic quantum materials, where nonlocal interactions are of particular interest. High-order linked-cluster expansions provide access the solution of the eigenvalue problem for the infinite system, yet rely on the computation of high-dimensional oscillatory lattice sums with a graph structure, only approachable with Monte Carlo methods so far. This work resolves this issue, rendering all required graph lattice sums, referred to as graph zeta functions for kernels involving power-laws, computable. The resulting method reduces the evaluation time for state-of-the art series expansions from tenthousands of core-hours to minutes. After factorizing the lattice sum over blocks, each block is evaluated by the cheapest available strategy depending on its treewidth $\mathrm{tw}$. Basic blocks admit analytic forms in terms of generalized zeta functions. Series-parallel blocks with $\mathrm{tw}\le 2$ can be computed at linear cost in the number of graph nodes and in the size of the momentum grid using a semi-analytical algebra based on Epstein zeta functions and rapidly decaying Fourier series. Finally, for $\mathrm{tw}>2$, the method is combined with tensor-network bucket elimination yielding polynomial scaling of numerical work and memory in momentum grid size with exponents only growing with $\mathrm{tw}$ rather than with the number of vertices. Through use of FFT, the full momentum grid is recovered at the cost of a single momentum evaluation. We provide a detailed analysis of the precision and runtime of our method against analytic and numerical benchmarks. We further reproduce published Monte Carlo data for the transverse-field Ising model on different 1D, 2D, and 3D lattices, obtaining full agreement.

math.NACross-listedarXiv:2609.18918•Sep 17, 2026•0 citations

Sign Problem in Quantum Monte Carlo Simulation

Gaopei Pan, Zi Yang Meng

Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.

arXiv:2204.08777•Apr 19, 2022•7 citations

Sign-optimized Quantum Monte Carlo

Julius S. Herz, Robin Schäfer, M. G. Gonzalez +1 more

The sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.

arXiv:2607.24679•Jul 27, 2026•0 citations

Stochastic series expansion quantum Monte Carlo for Rydberg arrays

Ejaaz Merali, Isaac J. S. De Vlugt, Roger G. Melko

Arrays of Rydberg atoms are a powerful platform to realize strongly-interacting quantum many-body systems. A common Rydberg Hamiltonian is free of the sign problem, meaning that its equilibrium properties are amenable to efficient simulation by quantum Monte Carlo (QMC). In this paper, we develop a Stochastic Series Expansion QMC algorithm for Rydberg atoms interacting on arbitrary lattices. We describe a cluster update that allows for the efficient sampling and calculation of physical observables for typical experimental parameters, and show that the algorithm can reproduce experimental results on large Rydberg arrays in one and two dimensions.

arXiv:2107.00766•SciPost Physics Core•Apr 5, 2024•9 citations
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.
Due to the intrinsic complexity of the quantum many-body problem, quantum Monte Carlo algorithms and their corresponding Monte Carlo configurations can be defined in various ways. Configurations corresponding to few Feynman diagrams often lead to severe sign problems. On the other hand, computing the configuration weight becomes numerically expensive in the opposite limit in which many diagrams are grouped together. Here we show that for continuous-time quantum Monte Carlo in the hybridization expansion the efficiency can be substantially improved by dividing the local impurity trace into fragments, which are then sampled individually. For this technique, which also turns out to preserve the fermionic sign, a modified update strategy is introduced in order to ensure ergodicity. Our (super)state sampling is particularly beneficial to calculations with many ddd orbitals and general local interactions, such as full Coulomb interaction. For illustration, we reconsider the simple albeit well-known case of a degenerate three-orbital model at low temperatures. This allows us to quantify the coherence properties of the ``spin-freezing'' crossover, even close to the Mott transition.
Over the past decade, high-order series expansions based on linked-cluster methods have become an important tool for studying low-energy properties of gapped quantum systems with long-range interactions. We introduce a deterministic framework that removes a central computational bottleneck of this method. Our graph zeta method replaces the costly and statistically noisy Monte Carlo (MC) evaluation of high-dimensional lattice sums by a systematic, high-precision computation that delivers series coefficients within minutes on standard desktop hardware. The full momentum-dependent series is obtained in a single calculation, enabling high-resolution excitation spectra throughout the Brillouin zone. Building on the companion paper [1], the method reformulates graph-embedding sums as graph zeta functions and decomposes them into blocks classified by their treewidth tw. Low-treewidth blocks (tw≤2\leq2≤2) admit closed expressions based on Epstein zeta functions, while higher-treewidth blocks (tw>2>2>2) are evaluated using tensor-network bucket elimination. We benchmark the approach for transverse-field Ising models with power-law interactions in 1d, 2d, and 3d, reproducing previous MC results at a fraction of the computational cost while enabling substantially denser parameter sampling. An open-source implementation makes the method directly applicable to general interactions and large parameter scans. As an application, we compare microscopic interaction models for the stacked quasi-2d transverse-field Ising triangular-lattice antiferromagnet KTmSe2_22​ and find that a model including dipolar interactions best describes existing experimental data. The graph zeta method thus turns high-order linked-cluster expansions into a practical and deterministic tool for fast quantitative momentum-resolved modeling of short- and long-range quantum matter.
Taming the exponential increase of the Hilbert space dimension with system size in the simulation of gapped quantum lattice models is of the highest relevance for understanding and designing exotic quantum materials, where nonlocal interactions are of particular interest. High-order linked-cluster expansions provide access the solution of the eigenvalue problem for the infinite system, yet rely on the computation of high-dimensional oscillatory lattice sums with a graph structure, only approachable with Monte Carlo methods so far. This work resolves this issue, rendering all required graph lattice sums, referred to as graph zeta functions for kernels involving power-laws, computable. The resulting method reduces the evaluation time for state-of-the art series expansions from tenthousands of core-hours to minutes. After factorizing the lattice sum over blocks, each block is evaluated by the cheapest available strategy depending on its treewidth tw\mathrm{tw}tw. Basic blocks admit analytic forms in terms of generalized zeta functions. Series-parallel blocks with tw≤2\mathrm{tw}\le 2tw≤2 can be computed at linear cost in the number of graph nodes and in the size of the momentum grid using a semi-analytical algebra based on Epstein zeta functions and rapidly decaying Fourier series. Finally, for tw>2\mathrm{tw}>2tw>2, the method is combined with tensor-network bucket elimination yielding polynomial scaling of numerical work and memory in momentum grid size with exponents only growing with tw\mathrm{tw}tw rather than with the number of vertices. Through use of FFT, the full momentum grid is recovered at the cost of a single momentum evaluation. We provide a detailed analysis of the precision and runtime of our method against analytic and numerical benchmarks. We further reproduce published Monte Carlo data for the transverse-field Ising model on different 1D, 2D, and 3D lattices, obtaining full agreement.
Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.
The sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.
Arrays of Rydberg atoms are a powerful platform to realize strongly-interacting quantum many-body systems. A common Rydberg Hamiltonian is free of the sign problem, meaning that its equilibrium properties are amenable to efficient simulation by quantum Monte Carlo (QMC). In this paper, we develop a Stochastic Series Expansion QMC algorithm for Rydberg atoms interacting on arbitrary lattices. We describe a cluster update that allows for the efficient sampling and calculation of physical observables for typical experimental parameters, and show that the algorithm can reproduce experimental results on large Rydberg arrays in one and two dimensions.