Polynomial complexity despite the fermionic sign

Abstract

It is commonly believed that in quantum Monte Carlo approaches to fermionic many- body problems, the infamous sign problem generically implies prohibitively large computational times for obtaining thermodynamic-limit quantities. We point out that for convergent Feynman diagrammatic series evaluated with the Monte Carlo algorithm of [Rossi, arXiv:1612.05184], the computational time increases only polynomially with the inverse error on thermodynamic-limit quantities.