Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.09071

The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time

Aarif Chaudhary, Jonas Valenzuela, Sa Chin

Published Sep 8, 2026• 0 citations
arXivHTMLPDF

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(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.

DOI
10.48550/arxiv.2609.09071

Related papers

Understanding the sign problem from an exact path integral Monte Carlo model of interacting harmonic fermions

Siu A. Chin

This work shows that the recently discovered operator contraction identity for solving the discrete path integral of the harmonic oscillator can be applied equally to fermions in any dimension. This then yields an exactly solvable model for studying the sign problem where the path integral Monte Carlo energy at any time step for any number of fermions is known analytically or can be computed numerically. It is found that the sign problem is primarily a property of the free fermion propagator, but repulsive/attractive pairwise interactions can shift the sign problem to larger/smaller imaginary time but do not make it more severe than the non-interacting case. More surprisingly, one can prove analytically that the first closed-shell state in D dimension, with n = D + 1 fermions, has no sign problem at large imaginary time. Direct numerical simulations confirm that this is also true for higher closed-shell states in two and three dimensions. Fourth-order and newly found variable-bead algorithms are used to compute ground state energies of quantum dots with up to 110 electrons and are compared to results obtained by modern neural networks.

The Journal of Chemical Physics•Jun 11, 2026•0 citations

Newton's Identity in Finite-Bead Fermionic Partition Function

A. Chaudhary, J. Valenzuela

For non-interacting fermions in a harmonic trap, the partition function at any discrete number of imaginary time slices (or beads) and for any choice of short-time propagator admits an exact recursion relation derived directly from the contracted determinant form of the path integral. This finite-bead recursion is distinct from earlier continuum-limit recursions, which do not apply to the discrete time partition functions. By identifying a direct correspondence between this recursion and Newton's identity, application of a closed-form result from the theory of partitions provides an exact expression for the one-dimensional $n$-fermion finite-bead partition function. From this, the Thermodynamic and Hamiltonian energies and specific heats are analytically calculated for any $n$, $N$, $τ$, and propagator choice.

arXiv:2606.05442•Jun 3, 2026•0 citations

Understanding the sign problem from an exact Path Integral Monte Carlo model of interacting harmonic fermions

Sa Chin

This work shows that the recently discovered operator contraction identity for solving the discreet Path Integral of the harmonic oscillator can be applied equally to fermions in any dimension. This then yields an exactly solvable model for studying the sign problem where the Path Integral Monte Carlo energy at any time step for any number of fermions is known analytically, or can be computed numerically. It is found that the sign problem is primarily a property of the free fermion propagator, but repulsive/attractive pairwise interaction can shift the sign problem to larger/smaller imaginary time but does not make it more severe than the non-interacting case. More surprisingly, one can prove analytically that the first closed-shell state in $D$ dimension, with $n=D+1$ fermion, has no sign problem at large imaginary time. Direct numerical simulations confirm that this is also true for higher closed-shell states in two and three-dimension. Fourth-order and newly found variable-bead algorithms are used to compute ground state energies of quantum dots with up to 110 electrons and compared to results obtained by modern neural networks.

arXiv:2601.22559•Jan 30, 2026•0 citations

Simple proof that there is no sign problem in path integral Monte Carlo simulations of fermions in one dimension

Siu A. Chin

It is widely known that there is no sign problem in path integral Monte Carlo (PIMC) simulations of fermions in one dimension. As far as the author is aware, there is no direct proof of this in the literature. This work shows that the sign of the N-fermion antisymmetric free propagator is given by the product of all possible pairs of particle separations, or relative displacements. For a nonvanishing closed-loop product of such propagators, as required by PIMC, all relative displacements from adjacent propagators are paired into perfect squares, and therefore the loop product must be positive, but only in one dimension. By comparison, permutation sampling, which does not evaluate the determinant of the antisymmetric propagator exactly, remains plagued by a low-level sign problem, even in one dimension.

arXiv:2407.01618•Physical review. E•Jun 25, 2024•3 citations

Fermionic physics fromab initiopath integral Monte Carlo simulations of fictitious identical particles

Tobias Dornheim, Panagiotis B. Tolias, Simon Groth +3 more

The ab initio path integral Monte Carlo (PIMC) method is one of the most successful methods in statistical physics, quantum chemistry and related fields, but its application to quantum degenerate Fermi systems is severely hampered by an exponential computational bottleneck: the notorious fermion sign problem. Very recently, Xiong and Xiong [J. Chem. Phys. 157, 094112 (2022)] have suggested to partially circumvent the sign problem by carrying out simulations of fictitious systems guided by an interpolating continuous variable ξ ∈ [-1, 1], with the physical Fermi- and Bose-statistics corresponding to ξ = -1 and ξ = 1. It has been proposed that information about the fermionic limit might be obtained by calculations within the bosonic sector ξ > 0 combined with an extrapolation throughout the fermionic sector ξ < 0, essentially bypassing the sign problem. Here, we show how the inclusion of the artificial parameter ξ can be interpreted as an effective penalty on the formation of permutation cycles in the PIMC simulation. We demonstrate that the proposed extrapolation method breaks down for moderate to high quantum degeneracy. Instead, the method constitutes a valuable tool for the description of large Fermi-systems of weak quantum degeneracy. This is demonstrated for electrons in a 2D harmonic trap and for the uniform electron gas (UEG), where we find excellent agreement (∼0.5%) with exact configuration PIMC results in the high-density regime while attaining a speed-up exceeding 11 orders of magnitude. Finally, we extend the idea beyond the energy and analyze the radial density distribution (2D trap), as well as the static structure factor and imaginary-time density-density correlation function (UEG).

arXiv:2308.06071•The Journal of Chemical Physics•Oct 27, 2023•42 citations

Permutation blocking path integral Monte Carlo: a highly efficient approach to the simulation of strongly degenerate non-ideal fermions

Tobias Dornheim, Simon Groth, Alexey V. Filinov +1 more

Correlated fermions are of high interest in condensed matter (Fermi liquids, Wigner molecules), cold atomic gases and dense plasmas. Here we propose a novel approach to path integral Monte Carlo (PIMC) simulations of strongly degenerate non-ideal fermions at finite temperature by combining a fourth-order factorization of the density matrix with antisymmetric propagators, i.e., determinants, between all imaginary time slices. To efficiently run through the modified configuration space, we introduce a modification of the widely used continuous space worm algorithm, which allows for an efficient sampling at arbitrary system parameters. We demonstrate how the application of determinants achieves an effective blocking of permutations with opposite signs, leading to a significant relieve of the fermion sign problem. To benchmark the capability of our method regarding the simulation of degenerate fermions, we consider multiple electrons in a quantum dot and compare our results with other ab initio techniques, where they are available. The present permutation blocking PIMC approach allows us to obtain accurate results even for N = 20 electrons at low temperature and arbitrary coupling, where no other ab initio results have been reported, so far.

arXiv:1504.03859•New Journal of Physics•Jul 14, 2015•123 citations
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)O(n^2)O(n2) time, providing an exact and numerically stable scheme for reproducing the energies of the original (undoable) fermion PIMC simulation for n=104n=10^4n=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.
This work shows that the recently discovered operator contraction identity for solving the discrete path integral of the harmonic oscillator can be applied equally to fermions in any dimension. This then yields an exactly solvable model for studying the sign problem where the path integral Monte Carlo energy at any time step for any number of fermions is known analytically or can be computed numerically. It is found that the sign problem is primarily a property of the free fermion propagator, but repulsive/attractive pairwise interactions can shift the sign problem to larger/smaller imaginary time but do not make it more severe than the non-interacting case. More surprisingly, one can prove analytically that the first closed-shell state in D dimension, with n = D + 1 fermions, has no sign problem at large imaginary time. Direct numerical simulations confirm that this is also true for higher closed-shell states in two and three dimensions. Fourth-order and newly found variable-bead algorithms are used to compute ground state energies of quantum dots with up to 110 electrons and are compared to results obtained by modern neural networks.
For non-interacting fermions in a harmonic trap, the partition function at any discrete number of imaginary time slices (or beads) and for any choice of short-time propagator admits an exact recursion relation derived directly from the contracted determinant form of the path integral. This finite-bead recursion is distinct from earlier continuum-limit recursions, which do not apply to the discrete time partition functions. By identifying a direct correspondence between this recursion and Newton's identity, application of a closed-form result from the theory of partitions provides an exact expression for the one-dimensional nnn-fermion finite-bead partition function. From this, the Thermodynamic and Hamiltonian energies and specific heats are analytically calculated for any nnn, NNN, τττ, and propagator choice.
This work shows that the recently discovered operator contraction identity for solving the discreet Path Integral of the harmonic oscillator can be applied equally to fermions in any dimension. This then yields an exactly solvable model for studying the sign problem where the Path Integral Monte Carlo energy at any time step for any number of fermions is known analytically, or can be computed numerically. It is found that the sign problem is primarily a property of the free fermion propagator, but repulsive/attractive pairwise interaction can shift the sign problem to larger/smaller imaginary time but does not make it more severe than the non-interacting case. More surprisingly, one can prove analytically that the first closed-shell state in DDD dimension, with n=D+1n=D+1n=D+1 fermion, has no sign problem at large imaginary time. Direct numerical simulations confirm that this is also true for higher closed-shell states in two and three-dimension. Fourth-order and newly found variable-bead algorithms are used to compute ground state energies of quantum dots with up to 110 electrons and compared to results obtained by modern neural networks.
It is widely known that there is no sign problem in path integral Monte Carlo (PIMC) simulations of fermions in one dimension. As far as the author is aware, there is no direct proof of this in the literature. This work shows that the sign of the N-fermion antisymmetric free propagator is given by the product of all possible pairs of particle separations, or relative displacements. For a nonvanishing closed-loop product of such propagators, as required by PIMC, all relative displacements from adjacent propagators are paired into perfect squares, and therefore the loop product must be positive, but only in one dimension. By comparison, permutation sampling, which does not evaluate the determinant of the antisymmetric propagator exactly, remains plagued by a low-level sign problem, even in one dimension.
The ab initio path integral Monte Carlo (PIMC) method is one of the most successful methods in statistical physics, quantum chemistry and related fields, but its application to quantum degenerate Fermi systems is severely hampered by an exponential computational bottleneck: the notorious fermion sign problem. Very recently, Xiong and Xiong [J. Chem. Phys. 157, 094112 (2022)] have suggested to partially circumvent the sign problem by carrying out simulations of fictitious systems guided by an interpolating continuous variable ξ ∈ [-1, 1], with the physical Fermi- and Bose-statistics corresponding to ξ = -1 and ξ = 1. It has been proposed that information about the fermionic limit might be obtained by calculations within the bosonic sector ξ > 0 combined with an extrapolation throughout the fermionic sector ξ < 0, essentially bypassing the sign problem. Here, we show how the inclusion of the artificial parameter ξ can be interpreted as an effective penalty on the formation of permutation cycles in the PIMC simulation. We demonstrate that the proposed extrapolation method breaks down for moderate to high quantum degeneracy. Instead, the method constitutes a valuable tool for the description of large Fermi-systems of weak quantum degeneracy. This is demonstrated for electrons in a 2D harmonic trap and for the uniform electron gas (UEG), where we find excellent agreement (∼0.5%) with exact configuration PIMC results in the high-density regime while attaining a speed-up exceeding 11 orders of magnitude. Finally, we extend the idea beyond the energy and analyze the radial density distribution (2D trap), as well as the static structure factor and imaginary-time density-density correlation function (UEG).
Correlated fermions are of high interest in condensed matter (Fermi liquids, Wigner molecules), cold atomic gases and dense plasmas. Here we propose a novel approach to path integral Monte Carlo (PIMC) simulations of strongly degenerate non-ideal fermions at finite temperature by combining a fourth-order factorization of the density matrix with antisymmetric propagators, i.e., determinants, between all imaginary time slices. To efficiently run through the modified configuration space, we introduce a modification of the widely used continuous space worm algorithm, which allows for an efficient sampling at arbitrary system parameters. We demonstrate how the application of determinants achieves an effective blocking of permutations with opposite signs, leading to a significant relieve of the fermion sign problem. To benchmark the capability of our method regarding the simulation of degenerate fermions, we consider multiple electrons in a quantum dot and compare our results with other ab initio techniques, where they are available. The present permutation blocking PIMC approach allows us to obtain accurate results even for N = 20 electrons at low temperature and arbitrary coupling, where no other ab initio results have been reported, so far.