Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations
Top Cited Papers
- 4 May 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 94 (17) , 170201
- https://doi.org/10.1103/physrevlett.94.170201
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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The loop algorithmAdvances in Physics, 2003
- High-Temperature Superfluidity of Fermionic Atoms in Optical LatticesPhysical Review Letters, 2002
- Quantum phase transition from a superfluid to a Mott insulator in a gas of ultracold atomsNature, 2002
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- Exact Monte Carlo Method for Continuum Fermion SystemsPhysical Review Letters, 2000
- Vanishing of the negative-sign problem of quantum Monte Carlo simulations in one-dimensional frustrated spin systemsPhysical Review B, 1998
- Representation basis in quantum Monte Carlo calculations and the negative-sign problemPhysics Letters A, 1992
- Quantum Monte Carlo simulation method for spin systemsPhysical Review B, 1991
- Green’s function Monte Carlo for few fermion problemsThe Journal of Chemical Physics, 1982
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982