Quantum proofs

DOI10.1561/0400000068zbMATH Open1339.68094DBLPjournals/fttcs/VidickW16arXiv1610.01664OpenAlexW4206841129WikidataQ59792546 ScholiaQ59792546MaRDI QIDQ2808277FDOQ2808277

Authors: Thomas Vidick, John Watrous 

Publication date: 23 May 2016

Published in: Foundations and Trends in Theoretical Computer Science (Search for Journal in Brave)

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*.

Full work available at URL: https://arxiv.org/abs/1610.01664

Recommendations

• Quantum multi-prover interactive proof systems with limited prior entanglement.
• scientific article; zbMATH DE number 1979492
• scientific article
• Algorithms and Computation
• Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?

zbMATH Keywords

NPquantum proofsQMAQIMquantum interactive proof

Mathematics Subject Classification ID

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

Cited In (17)

• The Connes embedding problem: a guided tour
• Temporally unstructured quantum computation
• Distinguishing short quantum computations
• On quantum interactive proofs with short messages
• Efficient Quantum Algorithms for Testing Symmetries of Open Quantum Systems
• A quantum characterization of NP
• Quantum versus classical proofs and advice
• Proofs of proximity for distribution testing
• Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
• Ancilla dimension in quantum channel discrimination
• The complexity of translationally invariant spin chains with low local dimension
• Spectral representation of some computably enumerable sets with an application to quantum provability
• Bounds on the power of proofs and advice in general physical theories
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Classical verification of quantum proofs
• Quantum interactive proofs and the complexity of separability testing
• Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states

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)