title: Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations.
abstract: Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.
authors.affiliation: Theoretische Physik, ETH Zürich, CH-8093 Zürich, Switzerland.
authors.forename: Matthias
authors.initials: M
authors.lastname: Troyer
authors.forename: Uwe-Jens
authors.initials: UJ
authors.lastname: Wiese