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