Foundations and Trends® in Theoretical Computer Science > Vol 11 > Issue 1-2

Quantum Proofs

By Thomas Vidick, California Institute of Technology, USA, vidick@cms.caltech.edu | John Watrous, University of Waterloo, Canada, john.watrous@uwaterloo.ca

 
Suggested Citation
Thomas Vidick and John Watrous (2016), "Quantum Proofs", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 11: No. 1-2, pp 1-215. http://dx.doi.org/10.1561/0400000068

Publication Date: 31 Mar 2016
© 2016 T. Vidick and J. Watrous
 
Subjects
Computational Models and Complexity,  Computational complexity,  Quantum Computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Preliminary Notions
3. Non-Interactive Quantum Proofs
4. Single-Prover Quantum Interactive Proofs
5. Quantum Zero-Knowledge
6. Multi-Prover Quantum Interactive Proofs
Acknowledgments
References

Abstract

Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.

DOI:10.1561/0400000068
ISBN: 978-1-68083-126-9
228 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-127-6
228 pp. $260.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Preliminary Notions
3. Non-Interactive Quantum Proofs
4. Single-Prover Quantum Interactive Proofs
5. Quantum Zero-Knowledge
6. Multi-Prover Quantum Interactive Proofs
Acknowledgments
References

Quantum Proofs

Quantum Proofs provides an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, it discusses non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.

Quantum Proofs is mainly intended for non-specialists having a basic background in complexity theory and quantum information. A typical reader may be a student or researcher in either area desiring to learn about the fundamentals of the (actively developing) theory of quantum interactive proofs.

 
TCS-068