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?
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.Sign up to join this community
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.