Quantum Interactive Proofs with Competing Provers

Details Quantum Interactive Proofs with Competing Provers Quantum Interactive Proofs with Competing Provers

2004-12-22

arxiv.org/abs/cs/0412102v1

Computer Science

Computational Complexity

13 pages, to appear in STACS 2005

Scientific paper

This paper studies 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. We prove 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 our 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. We also show how to reduce the probability of error for some classes of quantum refereed games.

Affiliated with

Also associated with

No associations

Rating

Quantum Interactive Proofs with Competing Provers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Interactive Proofs with Competing Provers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Interactive Proofs with Competing Provers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-542951