Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations

By Matthias Troyer, Uwe-Jens Wiese. Physical Review Letters, 2004

1,097 citations recorded by the source corpus.

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.

Subfields: Atomic and Molecular Physics, and Optics, Condensed Matter Physics

View Paper: https://www.semanticscholar.org/paper/c44589bc215e06a4624e26e7ef6073bcf4922a05

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Condensed Matter Physics

Citations in the corpus

Machine learning quantum phases of matter beyond the fermion sign problem (2016, background): “However, the lack of a general systematic procedure for such transformations [8] preclude many, if not most, quantum Hamiltonians from being simulated with unbiased QMC methods.”
Quantum simulation of fundamental particles and forces (2023, background): “While ideas are being pursued to tame many ‘sign problems’ [11–13], they are believed to be NP-hard [14].”
Lattice gauge theory simulations in the quantum information era (2016, neutral): “Monte Carlo methods is severely limited [15].”
Quantum algorithms to simulate many-body physics of correlated fermions. (2017, background): “Except at half filling, quantum Monte Carlo methods suffer from sign problems which prevent them from simulating systems at very low temperatures [20].”
Digitized adiabatic quantum computing with a superconducting circuit (2015, background): “In general, non-stoquastic Hamiltonians are more difﬁcult to study classically, as Monte Carlo simulations fail to converge due to the “sign problem” [19].”
Quantum Simulation (2013, background): “For some quantum systems, especially fermionic and frustrated systems, the numerical evaluation of the integrals encounters the problem of sampling with non-positive-semidefinite weight functions, which is the so-called sign problem [see, e.g. (Troyer and Wiese, 2005)].”
On nonnegative unbiased estimators (2013, methodology): “This method typically scales exponentially poorly with the dimension of the sampling space (Troyer and Wiese, 2005), an issue referred to as the “sign problem” in the lattice quantum chromodynamics literature.”
Solving the quantum many-body problem with artificial neural networks (2016, background): “Examples of systems where existing approaches fail are however numerous, mostly due to the sign problem in QMC [9], and to the ineﬃciency of current compression approaches in high-dimensional systems.”
Half-metallic ferromagnets: From band structure to many-body effects (2007, methodology): “This means that the sign problem, which is the main obstacle for the application of the QMC method to fermionic problems (Troyer and Wiese, 2005), does not arise in this case.”