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 of projected entangled pair states.

Norbert Schuch1, Michael M Wolf, Frank Verstraete

  • 1Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, D-85748 Garching, Germany.

Physical Review Letters
|May 16, 2007
PubMed
Summary
This summary is machine-generated.

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

XYZ Integrability the Easy Way.

Journal of statistical physics·2026
Same author

Tangent Space Excitation Ansatz for Quantum Circuits.

Physical review letters·2026
Same author

Learning Mixed Quantum States in Large-Scale Experiments.

Physical review letters·2026
Same author

Quantum Circuits for Matrix-Product Unitaries.

Physical review letters·2026
Same author

Dynamical Complexity of Non-Gaussian Many-Body Systems with Dissipation.

Physical review letters·2025
Same author

Entanglement and the density matrix renormalization group in the generalized Landau paradigm.

Nature physics·2025
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

Creating Projected Entangled Pair States (PEPS) can solve certain computational problems, but simulating them and contracting tensor networks are computationally hard (#P-complete). PEPS can also approximate ground states of gapped Hamiltonians.

Area of Science:

  • Quantum Information Science
  • Computational Complexity Theory
  • Condensed Matter Physics

Background:

  • Projected Entangled Pair States (PEPS) are a powerful tool for representing quantum many-body states.
  • Understanding the computational complexity of tasks involving PEPS is crucial for their practical application.

Purpose of the Study:

  • To determine the computational power of preparing PEPS.
  • To analyze the complexity of classically simulating PEPS and contracting general tensor networks.
  • To explore the use of PEPS in approximating ground states of gapped Hamiltonians.

Main Methods:

  • Utilizing a duality between PEPS and postselection.
  • Leveraging existing results from quantum complexity theory.
  • Employing techniques for analyzing tensor network contraction.

Related Experiment Videos

Main Results:

  • Preparing PEPS is shown to be computationally powerful, capable of solving problems in the PP complexity class.
  • Classically simulating PEPS and contracting tensor networks are proven to be #P-complete.
  • PEPS can be effectively used to approximate ground states of gapped Hamiltonians.
  • The creation of PEPS for approximating ground states is computationally less demanding than creating arbitrary PEPS.

Conclusions:

  • The study establishes a clear complexity hierarchy for tasks involving PEPS.
  • PEPS offer a viable pathway for approximating complex quantum states while acknowledging the inherent computational challenges in simulation and contraction.
  • The duality with postselection provides a powerful framework for complexity analysis in this domain.