2025/12/12 by Hongrui Chen, Cambyse Rouzé, Chen, Hongrui +14
Computer Science · Mathematics · Physics and Astronomy · #Computational Physics (physics.comp-ph) #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Numerical Analysis (math.NA) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems
paper · pdf · doi:10.48550/arxiv.2512.12010
openalex publication_date 2025/12/12 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
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.