Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912761576947712 |
|---|---|
| author | Chen, Hongrui Rouzé, Cambyse Chen, Jielun Jiang, Jiaqing Scalet, Samuel O. Zhan, Yongtao Chan, Garnet Kin-Lic Ying, Lexing Tong, Yu |
| author_facet | Chen, Hongrui Rouzé, Cambyse Chen, Jielun Jiang, Jiaqing Scalet, Samuel O. Zhan, Yongtao Chan, Garnet Kin-Lic Ying, Lexing Tong, Yu |
| contents | We propose a randomized algorithm to compute the log-partition function of weakly interacting fermions with polynomial runtime in both the system size and precision. Although weakly interacting fermionic systems are considered tractable for many computational methods such as the diagrammatic quantum Monte Carlo, a mathematically rigorous proof of polynomial runtime has been lacking. In this work we first extend the proof techniques developed in previous works for proving the convergence of the cumulant expansion in periodic systems to the non-periodic case. A key equation used to analyze the sum of connected Feynman diagrams, which we call the tree-determinant expansion, reveals an underlying tree structure in the summation. This enables us to design a new randomized algorithm to compute the log-partition function through importance sampling augmented by belief propagation. This approach differs from the traditional method based on Markov chain Monte Carlo, whose efficiency is hard to guarantee, and enables us to obtain a algorithm with provable polynomial runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12010 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions Chen, Hongrui Rouzé, Cambyse Chen, Jielun Jiang, Jiaqing Scalet, Samuel O. Zhan, Yongtao Chan, Garnet Kin-Lic Ying, Lexing Tong, Yu Quantum Physics Numerical Analysis Mathematical Physics Computational Physics We propose a randomized algorithm to compute the log-partition function of weakly interacting fermions with polynomial runtime in both the system size and precision. Although weakly interacting fermionic systems are considered tractable for many computational methods such as the diagrammatic quantum Monte Carlo, a mathematically rigorous proof of polynomial runtime has been lacking. In this work we first extend the proof techniques developed in previous works for proving the convergence of the cumulant expansion in periodic systems to the non-periodic case. A key equation used to analyze the sum of connected Feynman diagrams, which we call the tree-determinant expansion, reveals an underlying tree structure in the summation. This enables us to design a new randomized algorithm to compute the log-partition function through importance sampling augmented by belief propagation. This approach differs from the traditional method based on Markov chain Monte Carlo, whose efficiency is hard to guarantee, and enables us to obtain a algorithm with provable polynomial runtime. |
| title | Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions |
| topic | Quantum Physics Numerical Analysis Mathematical Physics Computational Physics |
| url | https://arxiv.org/abs/2512.12010 |