Strong Parallel Repetition Theorem for Quantum XOR Proof Systems
arXiv:quant-ph/0608146
Abstract
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.
17 pages, no figures
References in corpus (1)
Cited by in corpus (11)
- Monogamy of nonlocal quantum correlations
- Parallel repetition: simplifications and the no-signaling case
- Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction
- Quantum Strategies and Local Operations
- Classical command of quantum systems via rigidity of CHSH games
- Entangled games are hard to approximate
- Public-key cryptography based on bounded quantum reference frames
- Rank-one Quantum Games
- Unconditionally-secure and reusable public-key authentication
- Properties of Local Quantum Operations with Shared Entanglement
- Entangled games do not require much entanglement (withdrawn)