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Δ), where
N is the system size,
ε the desired precision, and
Δ the interaction-graph degree. This becomes particularly severe in long-range systems, where
Δ≡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). For quantum partition functions at temperatures
β≤βsampling≡O(1), this improves to
O~(N3+1/Dε−3), where
D is the lattice dimension. The framework directly applies to long-range quantum systems with interactions
∝1/rα, including
2-local models with
α>2D.
We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of the abstract polymer model formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness. Published by the American Physical Society 2024
We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.
Long-range quantum systems, in which the interactions decay as 1 / r α , are of increasing interest due to the variety of experimental setups in which they naturally appear. Motivated by this, we study fundamental properties of long-range spin systems in thermal equilibrium, focusing on the weak regime of α > D . Our main result is a proof of analyticity of their partition functions at high temperatures, which allows us to construct a classical algorithm with subexponential runtime exp ( O ( log 2 ( N / ϵ ) ) ) that approximates the log-partition function to small additive error ϵ . As by-products, we establish the equivalence of ensembles and the Gaussianity of the density of states, which we verify numerically in both the weak and strong long-range regimes. This also yields constraints on the appearance of various classes of phase transitions, including thermal, dynamical, and excited-state ones. Our main technical contribution is the extension to the quantum long-range regime of the convergence criterion for cluster expansions of Kotecký and Preiss.
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable
A at time
t. By analyzing the convergence of the perturbative expansion in the interaction strength
λ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime
λ∣t∣2D+1=O(1), when the Hamiltonian is geometrically local on a
D-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to
λ∣t∣=O(1) with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to
λ∣t∣=O(1), modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.