🔢 mathematics

Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions

This paper presents a mathematically rigorous, randomized polynomial-time algorithm for computing the log-partition function of weakly interacting fermions by extending cumulant expansion convergence proofs to non-periodic systems and utilizing a tree-determinant expansion with importance sampling and belief propagation.

Original authors: Hongrui Chen, Cambyse Rouzé, Jielun Chen, Jiaqing Jiang, Samuel O. Scalet, Yongtao Zhan, Garnet Kin-Lic Chan, Lexing Ying, Yu Tong

Published 2026-09-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongrui Chen, Cambyse Rouzé, Jielun Chen, Jiaqing Jiang, Samuel O. Scalet, Yongtao Zhan, Garnet Kin-Lic Chan, Lexing Ying, Yu Tong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the microscopic world of electrons and atoms, scientists often try to predict how a collection of particles will behave when they are heated or cooled. To do this, they calculate a value called the partition function. Think of this number as a master key that unlocks the average properties of a system, such as its energy or how it responds to a magnetic field. For simple systems where particles do not interact, this calculation is straightforward. However, when particles push and pull on each other, the math becomes incredibly difficult. The interactions create a web of dependencies where changing one particle affects all the others, making the calculation of the partition function a monumental task that has long resisted efficient solutions.

For decades, researchers have relied on methods that work well in some cases but fail in others, often requiring so much computing power that they become impractical for large systems. A major hurdle has been the lack of a guaranteed, fast way to solve this problem for "weakly interacting" fermions—a specific type of particle, like electrons, that follows strict rules about how they can occupy space. While quantum computers have shown promise in this area, the question remained: can a standard classical computer, the kind found in offices and homes, solve this problem efficiently? Until now, the answer was no, or at least not with a mathematical guarantee that the time required would not explode as the system grew larger.

A team of researchers has now provided a definitive "yes" to that question. They have developed a new algorithm that can calculate the partition function for these weakly interacting fermionic systems in a time that grows reasonably with the size of the system. This is a significant leap forward because previous rigorous methods either took too long or only worked under very specific, limited conditions. The new approach does not just offer a guess or a simulation; it provides a mathematically proven path to the answer, ensuring that the time required to get a precise result stays manageable even as the number of particles increases.

The core of this breakthrough lies in how the researchers reorganized the problem. Instead of trying to count every possible way the particles could interact, which is like trying to count every grain of sand on a beach, they found a way to group these interactions into a simpler structure. They discovered that the complex sum of all interactions could be rearranged into a form that resembles a tree, where branches connect different parts of the system without forming confusing loops. This "tree" structure allowed them to use a technique called belief propagation, a method that passes information along the branches to build up the final answer step by step. Because the interactions between the particles are weak, the influence of distant parts of the system fades away quickly, making this tree-like approach highly effective.

The researchers proved that their method works as long as the interactions between particles are not too strong. They showed that the mathematical series they use to approximate the answer converges rapidly, meaning that they only need to calculate a relatively small number of terms to get a result that is accurate to any desired level of precision. By combining this rapid convergence with their tree-based sampling strategy, they created a randomized algorithm that can estimate the partition function with high confidence. The time it takes to run this algorithm is proportional to the number of particles and the desired precision, making it a polynomial-time solution. This means that if you double the size of the system, the time required to solve it increases by a predictable, manageable factor, rather than skyrocketing.

This work also addresses a long-standing debate about the power of quantum computers versus classical ones in this specific regime. Since the new classical algorithm is so efficient, it suggests that for weakly interacting fermions, there may not be a massive advantage to using a quantum computer to find the partition function. The classical method matches the performance of the best-known quantum approaches for this problem. Furthermore, the algorithm is versatile. It can handle systems where particles interact over long distances, provided the strength of that interaction drops off quickly enough with distance. It can also be used to calculate the average behavior of specific local parts of the system, such as the energy of a single electron in a large molecule, without needing to solve the entire system at once.

The implications of this finding extend beyond just solving a math puzzle. The ability to efficiently calculate these properties for weakly interacting systems is crucial for understanding materials in physics and chemistry, from superconductors to complex molecules. By providing a rigorous, fast, and classical way to compute these values, the researchers have opened the door to more accurate simulations of real-world materials. The method relies on the fact that in these systems, the particles are not tightly locked in a chaotic dance but are instead loosely connected, allowing their collective behavior to be untangled and understood through the new tree-based framework. This work stands as a proof that even in the complex quantum world, there are patterns that classical computers can follow to find the truth.

Technical Summary: Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions

1. Problem Statement

The paper addresses the computational challenge of estimating the log-partition function, $\log Z$ , for weakly interacting fermionic systems at a fixed inverse temperature $\beta$ . The system consists of $N$ fermionic modes on a $d$ -dimensional lattice, governed by a Hamiltonian $H = H_0 + V$ , where $H_0$ is a quadratic (free) Hamiltonian and $V$ represents a weak interaction potential.

While quantum Gibbs sampling has recently demonstrated that thermal states of such systems can be prepared in polynomial time, a mathematically rigorous classical algorithm with polynomial runtime for computing the partition function has remained unavailable. Existing classical approaches, such as diagrammatic quantum Monte Carlo (QMC), rely on Markov chain Monte Carlo (MCMC) methods whose efficiency depends on unknown mixing times, preventing rigorous polynomial-time guarantees. Conversely, rigorous cluster expansion methods have historically been limited to high-temperature spin systems or specific non-interacting limits, failing to directly apply to weakly interacting fermions where the unperturbed state is a correlated Gaussian state rather than a product state.

The goal is to provide a classical algorithm that approximates $\log Z$ to within an additive error of $\epsilon N$ (i.e., error $\epsilon$ per mode) with a runtime polynomial in the system size $N$ and the inverse precision $1/\epsilon$ .

2. Methodology

2.1 Cumulant Expansion and Convergence Analysis

The authors begin with the cumulant expansion of the log-partition function:
$\log(Z/Z_0) = \sum_{s=1}^{\infty} \frac{(-1)^s}{s!} \sum_{P_1, \dots, P_s \in \mathcal{P}} v_{P_1} \dots v_{P_s} \int_{[0,\beta]^s} d\tau_1 \dots d\tau_s \, E_c(\{P_i, \tau_i\}_{i \in [s]})$
where $E_c$ denotes the connected part of the time-ordered correlation function. Standard diagrammatic expansions express $E_c$ as a sum over connected Feynman diagrams. However, the number of such diagrams grows factorially ( $\sim (2s)!$ ), leading to quasi-polynomial complexity if evaluated term-by-term.

To overcome this, the paper introduces a tree-determinant expansion. This reorganizes the sum over connected Feynman diagrams into a sum over labeled trees (using tree-graph identities from rigorous quantum field theory). Specifically, the cumulant is expressed as:
$E_c(\{P_i, \tau_i\}) = \sum_{T \in \mathcal{T}([s])} \sum_{\chi \in A(T)} \alpha_{T,\chi} \left( \prod_{(i,j) \in T} g_{\tau_i, \tau_j}(P_i, P_j, \chi_{ij}) \right) h_\tau(P_1, \dots, P_s, T, \chi)$
Here, the sum is over trees $T$ rather than diagrams. The number of trees grows as $s^{s-2}$ (Cayley's formula), which, when combined with the $1/s!$ prefactor, results in exponential rather than factorial growth. The term $h_\tau$ encapsulates the remaining contractions as a linear combination of determinants of matrices constructed from the non-interacting Green's function.

2.2 Convergence Proof

The authors prove that this series converges exponentially fast when the interaction strength $U$ is below a threshold $C(\beta)$ independent of $N$ . The proof relies on two key technical components:

Determinant Bounds: Using a generalized Gram inequality and specific embedding maps for the Green's function, they establish a uniform bound on the determinants appearing in $h_\tau$ , showing they grow at most exponentially with $s$ .
Summability: By leveraging the $L_V$ -summability of the interaction potential and the $L_g$ -summability (or exponential decay) of the non-interacting Green's function, they bound the summation over interaction terms $P_1, \dots, P_s$ . The tree structure allows this summation to be bounded by a product of local factors, ensuring the $s$ -th order term scales as $N \cdot \rho^s$ for some $\rho < 1$ .

2.3 Randomized Algorithm via Importance Sampling

Since the series converges exponentially, it can be truncated at order $S = O(\log(1/\epsilon))$ . The challenge then becomes evaluating the truncated sum efficiently. Instead of brute-force summation, the authors propose a randomized importance-sampling algorithm:

Tree Sampling: A labeled tree $T$ is sampled uniformly (using Prüfer codes).
Variable Sampling: Conditional on the tree and imaginary times, the interaction terms $P_1, \dots, P_s$ are sampled from a distribution proportional to their absolute contribution. Due to the tree structure, this distribution forms a Markov Random Field (MRF) on a tree, which can be sampled efficiently using Belief Propagation (BP).
Estimator Construction: For each sample, an unbiased weight $w_s$ is computed. The final estimate is the average of these weights over many samples.

The variance of the estimator is bounded independently of $N$ (under the weak interaction condition), ensuring that $O(1/\epsilon^2)$ samples suffice to achieve the desired precision.

3. Key Contributions and Results

3.1 Main Theorems

Theorem 1.1 (Convergence): Establishes the exponential convergence of the cumulant expansion for geometrically local fermionic Hamiltonians when the interaction strength is below a system-size-independent threshold.
Theorem 1.2 (Finite-Temperature Algorithm): Provides a randomized classical algorithm that estimates $\log Z$ to additive error $\epsilon N$ with probability at least $2/3$ in time $\tilde{O}(N \epsilon^{-2})$ for geometrically local systems. For translation-invariant systems, the runtime improves to $\tilde{O}(\epsilon^{-2})$ , independent of $N$ .
Corollary 1.3 (Local Observables): Extends the algorithm to compute thermal expectation values of local observables with runtime $\tilde{O}(\epsilon^{-2})$ , independent of system size, by utilizing the log-partition function as a generating function.
Theorem 1.4 (General Interactions): Generalizes the results to long-range interactions provided they satisfy summability conditions ( $L_V$ and $L_g$ ), yielding a polynomial-time algorithm (though with a higher degree dependence on $N$ than the strictly local case).

3.2 Complexity Analysis

Query Complexity: The algorithm requires $O(|\mathcal{P}|^2 \epsilon^{-2} \text{polylog}(1/\epsilon))$ queries in the general case and $O(N \epsilon^{-2} \text{polylog}(N/\epsilon))$ for geometrically local potentials.
Runtime: When combined with the cost of computing the non-interacting Green's function (which is $O(N^2 \text{polylog}(1/\epsilon))$ generally, but $O(\text{polylog}(N/\epsilon))$ for finite-ranged $H_0$ ), the total runtime is polynomial in $N$ and $1/\epsilon$ .
Optimality: The linear dependence on $N$ for local systems is noted as essentially optimal, as reading the Hamiltonian itself requires linear time.

4. Significance and Claims

The paper claims to provide the first polynomial-time classical algorithm for computing the log-partition function of weakly interacting fermions. Its significance lies in several areas:

Bridging Physics and Rigorous Complexity: It successfully bridges the gap between physics-inspired diagrammatic methods (which lack rigorous runtime guarantees) and rigorous algorithmic techniques (which previously struggled with the correlated nature of fermionic ground states).
Overcoming the "Sign Problem" via Cancellations: Unlike bosonic or classical systems where perturbative expansions may diverge, the authors demonstrate that the fermionic anti-commutation relations induce cancellations that allow for a positive radius of convergence, even at low temperatures (provided interactions are weak).
Comparison to Quantum Algorithms: The results suggest that for weakly interacting fermions, there may not be a superpolynomial quantum advantage for estimating partition functions, as classical algorithms can match the polynomial scaling of recent quantum Gibbs sampling approaches.
Methodological Innovation: The combination of tree-determinant expansions with belief propagation for importance sampling offers a new paradigm for evaluating high-order perturbation series in quantum many-body systems, avoiding the mixing time issues inherent in MCMC-based diagrammatic QMC.

The authors remain modest regarding zero-temperature applications, noting that while their approach relies on Green's function decay (which holds for gapped systems), extending the algorithm to the ground state regime requires further investigation. They also clarify that their results apply to the weak interaction regime, where the interaction strength is small relative to the temperature and the non-interacting gap, and do not claim to solve the general strongly interacting case.