Efficient classical simulation of Fermi-Hubbard models with Kramers symmetry

Problem Statement

Quantum Monte Carlo (QMC) methods are the standard classical approach for simulating interacting fermionic systems, yet rigorous theoretical guarantees regarding their efficiency are scarce. While the absence of the "sign problem" is a necessary condition for efficient QMC, it is not sufficient to guarantee polynomial-time convergence of the underlying Markov chains. Furthermore, existing rigorous results for efficient classical simulation of fermionic systems are largely confined to high-temperature regimes, perturbative limits, or specific mappings to spin systems. There is a significant gap in understanding the computational complexity of strongly interacting fermionic systems, even when they are known to be sign-problem-free.

This work addresses the specific intersection of two structural properties: Kramers time-reversal symmetry (which ensures a sign-problem-free expansion) and the Lee-Yang zero-freeness theorem (which relates to the location of partition function zeros). The authors investigate whether this intersection allows for provably efficient classical algorithms for computing partition functions and ground energies in broad families of Fermi-Hubbard models.

Methodology

The authors develop a novel classical randomized algorithm based on a determinantal worm Markov chain. The methodology proceeds in three main stages:

1. Trotterization and Interaction Expansion:
   The partition function $Z = \text{Tr}(e^{-\beta H})$ is approximated using a discrete-time Trotter decomposition. The Hamiltonian $H$ is split into a free part $H_0$ and interaction terms $V_i$. The expansion of $\text{Tr}(L^M)$ (where $L$ is the Trotter step) is rewritten as a sum over subsets of "insertions" (interaction terms). Using Wick's theorem, each term in this sum is expressed as the determinant of a principal submatrix of a global Green's function matrix $G$.

   • Sign Positivity: The authors demonstrate that for Hamiltonians in the "attractive Kramers class," the matrix $G$ is quaternionic. A key property of quaternionic matrices is that their eigenvalues come in complex-conjugate pairs, ensuring that the determinant of any square submatrix formed by whole block rows and columns is non-negative. This establishes that the weights in the expansion are non-negative, avoiding the sign problem.

2. Enlarged Configuration Space (The Worm):
   Directly sampling the principal minors (where row and column indices are identical) is difficult. To facilitate efficient sampling, the authors introduce an enlarged configuration space. They add a small "pairing field" to the Hamiltonian, allowing for configurations where the set of selected block rows ($A$) and block columns ($B$) differ, provided $|A| = |B|$.

   • The weight of a configuration $(A, B)$ is proportional to $\lambda^{|A \setminus B|} \det G[A, B]$, where $\lambda$ is a small parameter.
   • Valid configurations (where $A=B$) correspond to the original partition function terms. The probability mass of these valid configurations remains constant (bounded below by a constant) even as $\lambda \to 0$, provided $\lambda$ is chosen appropriately.

3. Fast Mixing via Log-Concavity:
   The core technical contribution is proving that the Markov chain defined on this enlarged space mixes in polynomial time.

   • The authors construct a generating polynomial for the determinants $\det G[A, B]$. They prove that for quaternionic matrices, this polynomial is strongly log-concave.
   • They leverage recent results by Anari, Liu, Oveis Gharan, and Vinzant [ALOGV24] and Chen and Liu [CL26], which show that basis-exchange chains (and their "tilted" variants) mix rapidly for measures with strongly log-concave generating polynomials.
   • The pairing field introduces a "tilt" factor \lambda^{|A \setminus B|. The authors verify that this tilt satisfies the local spectral curvature conditions required by Chen and Liu [CL26] to preserve rapid mixing.

Key Contributions

• Polynomial-Time Algorithm: The paper provides the first rigorous proof of a polynomial-time classical algorithm for estimating the partition function of a broad family of interacting fermionic systems (specifically, attractive Kramers-invariant Hamiltonians).
• Determinantal Worm Chain: The authors introduce a "determinantal worm" Markov chain that extends the worm algorithm concept (previously used for spins and bosons) to fermionic systems with Kramers symmetry. Unlike previous fermionic worm attempts, this technique is systematically applicable to the entire Kramers class with provable convergence guarantees.
• Connection of Structural Properties: The work rigorously connects the absence of the sign problem (via Kramers symmetry) with the Lee-Yang zero-freeness property (via log-concavity of the generating polynomial) to establish efficient classical simulability.
• Scope of Applicability: The algorithm applies to:
  • Attractive Fermi-Hubbard models with real hopping amplitudes on any graph.
  • Repulsive Fermi-Hubbard models at half-filling on bipartite graphs (via particle-hole transformation).
  • Crucially, there are no restrictions on the strength or extensivity of the interactions.

Results

The main theorem states that for any Hamiltonian $H$ in the attractive Kramers class, there exists a randomized classical algorithm that estimates the partition function $Z$ to relative error $\epsilon$ in time $\text{poly}(N, r, \beta, \Lambda, 1/\epsilon)$, where $N$ is the number of modes, $r$ is the number of interaction terms, $\beta$ is the inverse temperature, and $\Lambda$ bounds the interaction strength.

Consequently, the algorithm can efficiently estimate:

• The free energy $F_\beta$ to additive error $\epsilon$.
• The ground state energy $E_0$ to additive error $\epsilon$ (by taking the limit $\beta \to \infty$).

The spectral gap of the Markov chain is proven to be at least $\lambda / (2|K|)$, ensuring polynomial mixing time.

Significance and Claims

The authors claim this work provides the first polynomial-time guarantees for fermionic quantum Monte Carlo. While the algorithm is not a variant of determinant quantum Monte Carlo (DQMC) itself, it rigorously validates decades of empirical success of DQMC and its variants on systems with Kramers symmetry.

The paper posits that the intersection of the Lee-Yang property and stoquasticity (or sign-problem-freeness) may be a broader guiding principle for identifying quantum systems that admit efficient classical simulation. The authors note that while they have solved the problem for the attractive Kramers class, other sign-problem-free fermionic systems (e.g., those with Majorana reflection positivity) that also possess the Lee-Yang property remain open for future exploration. The work suggests that structural properties enabling efficient simulation are not limited to spin systems but extend to strongly correlated fermionic matter.