HackerPapers

arXiv:cond-mat/0408370cond-mat.stat-mech

Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations

Matthias Troyer, Uwe-Jens Wiese

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.

arXiv comments
4 pages
Journal reference
Phys.Rev.Lett. 94 (2005) 170201
DOI
doi:10.1103/PhysRevLett.94.170201
Subjects
cond-mat.stat-mechStatistical Mechanics cond-mat.str-elStrongly Correlated Electrons cs.CCComputational Complexity hep-latHigh Energy Physics, Lattice physics.comp-phComputational Physics

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from May 2014 to Dec 2019.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Superconductivity Theory Under Attack 1 comment

    • Thanks for mentioning the term that I was able to find: https://en.wikipedia.org/wiki/Numerical_sign_problem https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.94... "Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations…

      acqqView on HNParent context

  2. YInMn Blue 1 comment

    • Here’s one example. Though it’s probably different from what you had in mind https://arxiv.org/abs/cond-mat/0408370

      jhrmnnView on HNParent context

  3. Google Project Lets You Program a Simulated Quantum Computer 1 comment

    • Maybe you mean subexponential time? Which is not much of an improvement. This is a question which I would like someone like Scott Aaronson to answer. The sign problem is NP-hard[1]. So it's not currently believed that quantum computers can actually help with the sign problem…

      balsamView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.