Strong Parallel Repetition Theorem for Quantum XOR Proof Systems

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

17 pages, no figures

Scientific paper

We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier's verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover's optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Strong Parallel Repetition Theorem for Quantum XOR Proof Systems 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 Strong Parallel Repetition Theorem for Quantum XOR Proof Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong Parallel Repetition Theorem for Quantum XOR Proof Systems will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-95353

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.