arXiv:2610.03893
Efficient Quantum Monte Carlo through Cluster Expansions
Jorge Sánchez-Segovia, Álvaro M. Alhambra
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$.
AI Summary
Deterministic cluster-expansion algorithms approximate quantum partition functions at high temperature, but enumerating connected clusters gives runtimes of the form $(N/\varepsilon)^{\mathcal O(\log\Delta)}$, becoming quasipolynomial for dense interaction graphs. This paper replaces enumeration with Markov-chain sampling of connected clusters contributing to $\log Z$, allowing signed or complex polymer weights. The estimator separates a positive normalization constant from a sign/phase-bearing observable. A strengthened Kotecký–Preiss condition, involving $|w_\gamma|^{1/2}$ rather than $|w_\gamma|$, bounds its variance. Single-polymer addition/deletion dynamics preserve cluster connectivity; canonical paths establish rapid mixing, while annealing estimates the normalization. Under regularity and uniform-local-weight assumptions, and access to a perfect local polymer sampler of expected cost $C_w$, the resulting additive-$\varepsilon$ approximation to $\log Z$ has expected runtime at most $\widetilde{\mathcal O}(C_w|V(G)|^4\varepsilon^{-3})$, with logarithmic overhead for confidence amplification. For $k$-local quantum Hamiltonians on a $D$-dimensional lattice with suitable power-law interactions, radial importance sampling supplies a constant-expected-cost local sampler. At sufficiently high temperature, $\beta\leq c_\beta/g$, the runtime becomes $\widetilde{\mathcal O}(N^{3+1/D}\varepsilon^{-3})$ for decay exponent $\alpha>kD$, including two-body models with $\alpha>2D$. The guarantees require stronger conditions than ordinary cluster-expansion convergence; they do not resolve the general sign problem. Extending the method to $\alpha>D$ remains open, and practical benchmarking is deferred. Applications to tensor-network corrections, circuits, and dynamics are discussed rather than worked out. Independent work noted in the paper reaches $\alpha>D$ with $\mathcal O(N^3\varepsilon^{-3})$ scaling for long-range partition functions.
Both models were also used in editing and revising the text.
Central claim may not hold: The abstract's general-polymer runtime omits the main theorem's perfect local-sampling oracle, its cost C_w, and additional weight assumptions. The efficient variance guarantee requires a square-root strengthening of ordinary cluster-expansion convergence, so it is not established throughout the ordinary convergence regime. The quantum application proof assumes a uniformly strong connected local skeleton that does not follow from its stated decay upper bounds. The normalization lemma's asserted incompatible-cluster bound is false under its stated Kotecký–Preiss hypothesis, leaving a substantive gap in the supplied justification of subsequent normalization and sampling bounds. The displayed estimator identity omits the size-m indicator needed when its sampling distribution includes clusters through size 2m.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.