A Caltech Library Service

Guest Column: The Quantum PCP Conjecture

Aharonov, Dorit and Arad, Itai and Vidick, Thomas (2013) Guest Column: The Quantum PCP Conjecture. ACM SIGACT News, 44 (2). pp. 47-79. ISSN 0163-5700. doi:10.1145/2491533.2491549.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 and multipartite entanglement, topology and the so-called phenomenon of topological order, 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Alternate Title:The Quantum PCP Conjecture
Additional Information:© 2013 ACM, Inc. T he authors would like to thank Fernando Brandão, Lior Eldar, Aram Harrow and Matt Hastings for very useful comments on this manuscript.
Issue or Number:2
Record Number:CaltechAUTHORS:20140910-135821275
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49555
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 21:43
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page