Using entanglement in quantum multi-prover interactive proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multiprover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra prover. Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.

Original languageEnglish (US)
Title of host publicationProceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages211-222
Number of pages12
DOIs
StatePublished - 2008
Event23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States
Duration: Jun 23 2008Jun 26 2008

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other23rd Annual IEEE Conference on Computational Complexity, CCC 2008
CountryUnited States
CityCollege Park, MD
Period6/23/086/26/08

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Using entanglement in quantum multi-prover interactive proofs'. Together they form a unique fingerprint.

Cite this