Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions
quant-ph, cs.NA, math-ph, math.MP, math.NA, physics.comp-ph
Submitted: 2025-12-12
Updated: 2026-09-24
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
Abstract
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.
Sources
- Quasi-adiabatic Continuation for Disordered Systems: Applications to Correlations, Lieb-Schultz-Mattis, and Hall Conductance
- An efficient and exact noncommutative quantum Gibbs sampler
- Polynomial-time classical sampling of high-temperature quantum Gibbs states
- High-Temperature Gibbs States are Unentangled and Efficiently Preparable
- High-Temperature Fermionic Gibbs States are Mixtures of Gaussian States
- Response functions of many-body condensed matter systems
- The ground state construction of the two-dimensional Hubbard model on the honeycomb lattice
- Quantum Thermal State Preparation
- Optimal quantum algorithm for Gibbs state preparation
- Simple and efficient end-to-end quantum thermal and ground state preparation
- Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
- Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems
- Renormalization group analysis of multi-band many-electron systems at half-filling
- The zero-temperature limit of the free energy density in many-electron systems at half-filling
- Non-Fermi Liquid Behaviors in the Hubbard model on the Honeycomb lattice
- High-temperature partition functions and classical simulatability of long-range quantum systems
- Lagrangian representation for fermionic linear optics
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity