Metraipolis › archive › dc_f50545192f35

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09071
License (as archived)
CC0-1.0
Archived
2026-10-16T16:01:18.656Z
SHA-256 of the archived text
ac2e3c2c8673c30fa57b14f23d80b5848171e270139450ca942de1b26eeda126
Stable URL of this page
https://metraipolis.com/documento/dc_f50545192f35

How to cite

The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time — arXiv:2609.09071 — arXiv (en), https://arxiv.org/abs/2609.09071 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f50545192f35 (Metraipolis archive dc_f50545192f35, sha256 ac2e3c2c8673c30fa57b14f23d80b5848171e270139450ca942de1b26eeda126)
BibTeX
@misc{dcf50545192f35,
  title = {The Path Integral Monte Carlo Sign Problem Is Not Always NP-Hard: Harmonic Fermions Can Be Solved in Quadratic Time — arXiv:2609.09071},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09071},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f50545192f35; sha256 ac2e3c2c8673c30fa57b14f23d80b5848171e270139450ca942de1b26eeda126},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09071. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\lambda$-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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-09 in physics.comp-ph).
Categorie arXiv: Computational Physics (physics.comp-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.09071 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:44:54.324Z dalla pagina https://arxiv.org/catchup/physics.comp-ph/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).