CaltechAUTHORS
Published June 2009 | Version Submitted
Journal Article Open

Using Entanglement in Quantum Multi-Prover Interactive Proofs

Creators

  • 1. ROR icon Tel Aviv University
  • 2. ROR icon National Institute of Informatics
  • 3. ROR icon University of California, Berkeley

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 multi-prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from one 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.

Additional Information

© 2009 Birkhäuser Verlag, Basel. Manuscript received 1 September 2008; Published 18 June 2009. We wish to thank Tsuyoshi Ito for suggesting that we include Theorem 5.2 in the paper to characterize the power of one-round public-coin quantum multiprover interactive proofs. Julia Kempe thanks Oded Regev and Amnon TaShma for useful discussions. Julia Kempe was partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848, by an Alon Fellowship of the Israeli Higher Council of Academic Research, by a grant of the Israeli Science Foundation and by a European Research Council (ERC) Starting Grant. Work of Julia Kempe and Thomas Vidick were partly done while at LRI, Université Paris-Sud, Orsay. Hirotada Kobayashi and Keiji Matsumoto were partially supported by the Strategic Information and Communications R&D Promotion Programme No. 031303020 of the Ministry of Internal Affairs and Communications of Japan and the Grant-in-Aid for Scientific Research (B) No. 18300002 of the Ministry of Education, Culture, Sports, Science and Technology of Japan.

Attached Files

Submitted - 0711.3715.pdf

Files

0711.3715.pdf

Files (225.5 kB)

Name Size Download all
md5:22168f5a0339a10007b40d32ccf24dca
225.5 kB Preview Download

Additional details

Identifiers

Eprint ID
104766
Resolver ID
CaltechAUTHORS:20200805-150138118

Related works

Describes
https://arxiv.org/abs/0711.3715 (URL)
https://resolver.caltech.edu/CaltechAUTHORS:20140910-083116800 (URL)

Funding

European Research Council (ERC)
015848
Israeli Higher Council of Academic Research
Israel Science Foundation
Ministry of Internal Affairs and Communications (Japan)
031303020
Ministry of Education, Culture, Sports, Science and Technology (MEXT)
18300002

Dates

Created
2020-08-05
Created from EPrint's datestamp field
Updated
2021-11-16
Created from EPrint's last_modified field