I've reading up on the numerical sign problem, and how a general solution is NP-Hard. I can't seem to find a proof of this, though.

Does anyone know where I can find a proof that the numerical sign problem is NP-Hard?


A proof is purportedly offered in the paper: "Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations". Click here for the arXiv link. Here is the 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 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.

Apparently the folks in statistical mechanics are far more familiar than I am with this. This post on the Physics StackExchange talks about the sign problem, too---and here as well.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.