The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time
Abstract
In the Path Integral Monte Carlo (PIMC) simulation of fermions in a harmonic trap, with and without pairwise harmonic interactions, the partition functions for any discrete number of imaginary time slices (or beads) and for any choice of the short-time propagator can be analytically obtained from the contracted determinant form of the propagator. This work shows that the resulting recursion relation can be reformulated in the λ-ring language, yielding a closed-form finite-bead partition function in two dimensions in terms of permutation statistics. This closed-form partition function can be evaluated by a special algorithm in O(n2) time, providing an exact and numerically stable scheme for reproducing the energies of the original (undoable) fermion PIMC simulation for n=104 or more fermions. This result provides a concrete framework in which the numerical instability of the sign problem is completely bypassed, and serves as a counterexample to the prevailing view that all truly fermionic PIMC sign problems are NP-hard.
Related
- The quadratic density response function for non-interacting fermions at arbitrary temperature
- Fermions and the Tsirelson Problem in Real Quantum Theory
- Redesigning the linear--quadratic--Gaussian cost function for feedback cooling of a quantum harmonic oscillator
- An Integral Equation for the Surface Current in the Problem of the Natural Modes of a Waveguide Containing a Resistive Film
- A High-Order Discretization Scheme for Surface Integral Equations for Analyzing the Electroencephalography Forward Problem
BibTeX
@misc{chaudhary2026path,
title = {{The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time}},
author = {Aarif Chaudhary and Jonas Valenzuela and Siu A. Chin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09071},
eprint = {2609.09071},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09071},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time
AU - Aarif Chaudhary
AU - Jonas Valenzuela
AU - Siu A. Chin
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09071
UR - https://arxiv.org/abs/2609.09071
AB - In the Path Integral Monte Carlo (PIMC) simulation of fermions in a harmonic trap, with and without pairwise harmonic interactions, the partition functions for any discrete number of imaginary time slices (or beads) and for any choice of the short-time propagator can be analytically obtained from the contracted determinant form of the propagator. This work shows that the resulting recursion relation can be reformulated in the λ-ring language, yielding a closed-form finite-bead partition function in two dimensions in terms of permutation statistics. This closed-form partition function can be evaluated by a special algorithm in O(n^2) time, providing an exact and numerically stable scheme for reproducing the energies of the original (undoable) fermion PIMC simulation for n=10^4 or more fermions. This result provides a concrete framework in which the numerical instability of the sign problem is completely bypassed, and serves as a counterexample to the prevailing view that all truly fermionic PIMC sign problems are NP-hard.
ER -