Access Restriction

Author Arad, Itai ♦ Vidick, Thomas ♦ Aharonov, Dorit
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 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.
Description Affiliation: School of Engineering and Computer Science, The Hebrew University, Jerusalem, Israel (Aharonov, Dorit) || Centre for Quantum Technologies, National University of Singapore, Singapore (Arad, Itai) || Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA (Vidick, Thomas)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-06-30
Publisher Place New York
Journal ACM SIGACT News (SIGA)
Volume Number 44
Issue Number 2
Page Count 33
Starting Page 47
Ending Page 79

Open content in new tab

   Open content in new tab
Source: ACM Digital Library