Chicago Journal of Theoretical Computer Science

Volume 2013

Article 11

Published by the Department of Computer Science, The University of Chicago.

Coherent state exchange in multi-prover quantum interactive proof systems

Debbie Leung
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ont., Canada
wcleung AT uwaterloo DOT ca

Ben Toner
School of Physics
University of Melbourne
bentoner AT bentoner DOT com


John Watrous
School of Computer Science
University of Waterloo
john DOT watrous AT uwaterloo DOT ca

August 13, 2013


We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches one. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.

Submitted December 17, 2012, revised August 9, 2013; published August 13, 2013.

DOI: 10.4086/cjtcs.2013.011

[] Article 10 [] Article 12
[back] Volume 2013 [back] Published articles
[CJCTS home]