We propose a randomized algorithm to compute the log-partition function of weakly interacting fermions with polynomial runtime in both the system size and precision. Although weakly interacting fermionic systems are considered tractable for many computational methods such as the diagrammatic quantum Monte Carlo, a mathematically rigorous proof of polynomial runtime has been lacking. In this work we first extend the proof techniques developed in previous works for proving the convergence of the cumulant expansion in periodic systems to the non-periodic case. A key equation used to analyze the sum of connected Feynman diagrams, which we call the tree-determinant expansion, reveals an underlying tree structure in the summation. This enables us to design a new randomized algorithm to compute the log-partition function through importance sampling augmented by belief propagation. This approach differs from the traditional method based on Markov chain Monte Carlo, whose efficiency is hard to guarantee, and enables us to obtain a algorithm with provable polynomial runtime.
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.
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 present a technique that enables the evaluation of perturbative expansions based on one-loop-renormalized vertices up to large expansion orders. Specifically, we show how to compute large-order corrections to the random phase approximation in either the particle-hole or particle-particle channels. The algorithm's efficiency is achieved by the summation over contributions of all symmetrized Feynman diagram topologies using determinants, and by integrating out analytically the two-body long-range interactions in order to yield an effective zero-range interaction. Notably, the exponential scaling of the algorithm as a function of perturbation order leads to a polynomial scaling of the approximation error with computational time for a convergent series. To assess the performance of our approach, we apply it to the nonperturbative regime of the square-lattice fermionic Hubbard model away from half-filling and report, as compared to the bare interaction expansion algorithm, significant improvements of the Monte Carlo variance as well as the convergence properties of the resulting perturbative series.
Quantum computers hold the potential to revolutionise the simulation of quantum many-body systems, with profound implications for fundamental physics and applications like molecular and material design. However, demonstrating quantum advantage in simulating quantum systems of practical relevance remains a significant challenge. In this work, we introduce a quantum algorithm for preparing Gibbs states of interacting fermions on a lattice with provable polynomial resource requirements. Our approach builds on recent progress in theoretical computer science that extends classical Markov chain Monte Carlo methods to the quantum domain. We derive a bound on the mixing time for quantum Gibbs state preparation by showing that the generator of the quantum Markovian evolution is gapped at any temperature up to a maximal interaction strength. This enables the efficient preparation of low-temperature states of weakly interacting fermions and the calculation of their free energy. We present exact numerical simulations for small system sizes that support our results and identify well-suited algorithmic choices for simulating the Fermi-Hubbard model beyond our rigorous guarantees.
We develop a numerically exact method for the summation of irreducible Feynman diagrams for fermionic self-energy in the thermodynamic limit. The technique, based on the diagrammatic determinant Monte Carlo and its recent extension to connected diagrams, allows us to reach high $(\ensuremath{\sim}10)$ orders of the weak-coupling expansion for the self-energy of the two-dimensional Hubbard model. Access to high orders reveals a nontrivial analytic structure of the self-energy and enables its controlled reconstruction with arbitrary momentum resolution in the nonperturbative regime of essentially strong correlations, which has recently been reached with ultracold atoms in optical lattices.
Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of processes: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for several non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can prepare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.