Using entanglement in quantum multi-prover interactive proofs

Julia Kempe; Hirotada Kobayashi; Keiji Matsumoto; Thomas Vidick

doi:10.1109/CCC.2008.6

Using entanglement in quantum multi-prover interactive proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages	211-222
Number of pages	12
DOIs	https://doi.org/10.1109/CCC.2008.6
State	Published - 2008
Event	23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States Duration: Jun 23 2008 → Jun 26 2008

Publication series

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

Other

Other	23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Country/Territory	United States
City	College Park, MD
Period	6/23/08 → 6/26/08

ASJC Scopus subject areas

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2008.6

Cite this

Using entanglement in quantum multi-prover interactive proofs. / Kempe, Julia; Kobayashi, Hirotada; Matsumoto, Keiji et al.
Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. 2008. p. 211-222 4558824 (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kempe, J, Kobayashi, H, Matsumoto, K & Vidick, T 2008, Using entanglement in quantum multi-prover interactive proofs. in Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008., 4558824, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 211-222, 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, MD, United States, 6/23/08. https://doi.org/10.1109/CCC.2008.6

@inproceedings{7617284d91684bcf9949e4d7908454d5,

title = "Using entanglement in quantum multi-prover interactive proofs",

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.",

author = "Julia Kempe and Hirotada Kobayashi and Keiji Matsumoto and Thomas Vidick",

year = "2008",

doi = "10.1109/CCC.2008.6",

language = "English (US)",

isbn = "9780769531694",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "211--222",

booktitle = "Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008",

note = "23rd Annual IEEE Conference on Computational Complexity, CCC 2008 ; Conference date: 23-06-2008 Through 26-06-2008",

}

TY - GEN

T1 - Using entanglement in quantum multi-prover interactive proofs

AU - Kempe, Julia

AU - Kobayashi, Hirotada

AU - Matsumoto, Keiji

AU - Vidick, Thomas

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=51749107495&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51749107495&partnerID=8YFLogxK

U2 - 10.1109/CCC.2008.6

DO - 10.1109/CCC.2008.6

M3 - Conference contribution

AN - SCOPUS:51749107495

SN - 9780769531694

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 211

EP - 222

BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

Y2 - 23 June 2008 through 26 June 2008

ER -

Using entanglement in quantum multi-prover interactive proofs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this