Quantum Interactive Proofs with Competing Provers - Gus Gutoski

This talk introduces quantum refereed games, which are quantum interactive proof systems with two competing provers: one that tries to convince the verifier to accept and the other that tries to convince the verifier to reject. A language L is said to have a quantum refereed game if there exists a verifier that, for optimal prover strategies, correctly accepts or rejects the input with high probability. I will show that every language having an ordinary quantum interactive proof system also has a quantum refereed game in which the verifier exchanges just one round of messages with each prover. A key part of this result proof is the fact that there exists a single quantum measurement that reliably distinguishes between mixed states chosen arbitrarily from disjoint convex sets having large minimal trace distance from one another. Time permitting, I will also show how to reduce the probability of error for some classes of quantum refereed games.