2004/08/16 by Matthias Troyer, Uwe-Jens Wiese · 6 citations
Physics and Astronomy · Computer Science · #cond-mat.stat-mech #cond-mat.str-el #cs.CC #hep-lat #physics.comp-ph
paper · pdf · doi:10.1103/physrevlett.94.170201
published as Phys.Rev.Lett. 94 (2005) 170201 · 4 pages
arxiv created 2004/08/16 · arxiv updated 2009/12/01
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 NP-hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP (nondeterministic polynomial) in polynomial time.