Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations.

Matthias Troyer1, Uwe-Jens Wiese

  • 1Theoretische Physik, ETH Zürich, CH-8093 Zürich, Switzerland.

Physical Review Letters
|May 21, 2005
PubMed
Summary

Solving the quantum fermion sign problem is proven to be NP-hard. This means a general polynomial-time solution is unlikely, impacting simulations of complex quantum systems.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Acceleration without Disruption: DFT Software as a Service.

Journal of chemical theory and computation·2024
Same author

Accelerating Computational Materials Discovery with Machine Learning and Cloud High-Performance Computing: from Large-Scale Screening to Experimental Validation.

Journal of the American Chemical Society·2024
Same author

High-throughput ab initio reaction mechanism exploration in the cloud with automated multi-reference validation.

The Journal of chemical physics·2023
Same author

A fast MR fingerprinting simulator for direct error estimation and sequence optimization.

Magnetic resonance imaging·2023
Same author

Practical quantum advantage in quantum simulation.

Nature·2022
Same author

From quantum link models to D-theory: a resource efficient framework for the quantum simulation and computation of gauge theories.

Philosophical transactions. Series A, Mathematical, physical, and engineering sciences·2021

Area of Science:

  • Quantum physics
  • Computational complexity theory
  • Quantum many-body systems

Background:

  • Quantum Monte Carlo (QMC) simulations are powerful for bosons but face the 'sign problem' with fermions.
  • The fermion sign problem leads to exponential computational cost, hindering exact simulations of correlated quantum systems.
  • A polynomial-time solution for the sign problem is crucial for advancing quantum system simulations.

Purpose of the Study:

  • To investigate the computational complexity of the fermion sign problem in Quantum Monte Carlo simulations.
  • To determine if a generic, efficient (polynomial-time) solution to the sign problem is feasible.
  • To establish the theoretical limits for simulating fermionic quantum systems.

Main Methods:

  • The study employs techniques from computational complexity theory.

Related Experiment Videos

  • It proves the fermion sign problem is nondeterministic polynomial (NP) hard.
  • This establishes a formal link between the sign problem and other NP-hard problems.

    • Main Results:

    • The fermion sign problem is demonstrated to be NP-hard.
    • This implies that a general polynomial-time algorithm to solve it is highly unlikely.
    • The findings suggest that unbiased, exact simulations of large fermionic systems remain computationally intractable.

    Conclusions:

    • A generic polynomial-time solution to the fermion sign problem is almost certainly unattainable.
    • The computational difficulty of simulating fermionic systems is formally established.
    • This research sets fundamental limits on the exact numerical simulation of correlated quantum matter.