Quantum proofs

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Quantum algorithms and complexity in the theory of computing (68Q12)

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 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 class{QSZK}, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.

Review text

Quantum interactive proof systems use quantum information, interaction and proofs. The superposition principle appears to offer computational advantage over classical proof strings. In the interactive proof system setting, one can consider one verifier and several provers that exchange and process quantum information, giving rise to quantum complexity classes. NEWLINENEWLINENEWLINE The monograph under review is a survey of many known results concerning quantum proofs. Classical interactive proof systems depart from non-interactive settings when the verifier makes use of randomness, satisfied with statistical evidence. NEWLINENEWLINENEWLINE Chapter two follows the introductory Chapter one and deals with some preliminary material of quantum computing and complexity theory. NEWLINENEWLINENEWLINE Chapter three introduces the class QMA of languages that have efficiently verifiable quantum proofs. In QMA are the decision problems whose positive instances have quantum proofs that can be verified by an efficient quantum procedure, it satisfies many features of NP. The class QIP corresponds to single-prover quantum interactive proofs. They can be parallelised to three message interactions by using the superposition principle. Zero-interactions proofs are related to the non-cloning theorem. NEWLINENEWLINENEWLINE Chapter four deals with single-prover quantum interactive proof systems. NEWLINENEWLINENEWLINE Chapter five describes the class QSZK of quantum zero-knowledge interactive proofs. The difference to the classical systems is indicated. For quantum systems it is difficult to extend key techniques such as rewinding. Known quantum analogues are presented. NEWLINENEWLINENEWLINE Chapter six deals with multi-prover interactive proofs. The entanglement of different provers is investigated. This entanglement goes against the usual intuition on which classical systems are built. NEWLINENEWLINENEWLINE The survey is intended for non-specialists, however, the reader is required to have some basic knowledge in quantum computing as well as complexity theory. Full proofs of the main results are not included, instead detailed sketches highlight the ideas behind the proofs to simplify the reading. Each chapter ends with notes and references for the discussed results, a brief survey of related results and some indications to the literature. An index is not included. The monograph represents an up-to-date survey of the domain of quantum proofs and is recommended to anyone who is interested in this topic.

Recommendations

Cited in

(21)

This page was built for publication: Quantum proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808277)