loading...
Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.24Twenty-Second Annual IEEE Conference ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Richard Cleve, University of Waterloo, Canada
William Slofstra, University of California, Berkeley, USA
Falk Unger, CWI, the Netherlands
Sarvagya Upadhyay, University of Waterloo, Canada
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.
Citation:
Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay, "Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems," ccc, pp.109-114, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions