The Quantum PCP Conjecture

Abstract

The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics, the global nature of entanglement and its topological properties, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.

45 pages, 4 figures, an enhanced version of the SIGACT guest column from Volume 44 Issue 2, June 2013

References in corpus (6)

• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• The power of quantum systems on a line
• Entanglement renormalization and topological order
• Quantum NP - A Survey
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• One-Sided Error QMA with Shared EPR Pairs -- A Simpler Proof

Cited by in corpus (21)

• Decoherence in adiabatic quantum computation
• Quantum Hamiltonian Complexity
• Robust self-testing of many-qubit states
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• A Survey of Quantum Property Testing
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• A simple proof of the detectability lemma and spectral gap amplification
• A quantum primality test with order finding
• Robustness of QMA against witness noise
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Topological graph states and quantum error correction codes
• Optimizing sparse fermionic Hamiltonians
• Hamiltonian sparsification and gap-simulations
• Quantum Merlin Arthur with Exponentially Small Gap
• The pair-flip model: a very entangled translationally invariant spin chain
• Quantum Circuit Depth Lower Bounds For Homological Codes
• Constant-Soundness Interactive Proofs for Local Hamiltonians
• On the Complexity of Two Dimensional Commuting Local Hamiltonians
• Local Hamiltonians with Approximation-Robust Entanglement
• A multiprover interactive proof system for the local Hamiltonian problem
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability