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 timepositive aspects of prior entanglement and show how it can be used to parallelize any multi-prover quantum interactive proof system to aone-round system withperfect 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.

Authors and Affiliations

1. School of Computer Science, Tel-Aviv University, Tel-Aviv, 69978, Israel

   Julia Kempe

2. Principles of Informatics Research Division, National Institute of Informatics, Tokyo, 101-8430, Japan

   Hirotada Kobayashi & Keiji Matsumoto

3. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA, 94720, USA

   Thomas Vidick

Corresponding author

Correspondence toJulia Kempe.

Manuscript received 1 September 2008

Reprints and permissions