A parallel repetition theorem for entangled two-player one-round games under product distributions

Abstract

We show a parallel repetition theorem for the entangled value ${\omega }^{\ast }(G)$ of any two-player one-round game $G$ where the questions $(x,y)\in \mathcal{X}\times \mathcal{Y}$ to Alice and Bob are drawn from a product distribution on $\mathcal{X}\times \mathcal{Y}$. We show that for the $k$-fold product $G^k$ of the game $G$ (which represents the game $G$ played in parallel $k$ times independently), ${\omega }^{\ast }(G^k)={\left(1-(1-{\omega }^{\ast }(G){)}^3\right)}^{\Omega \left(\frac{k}{\log (|\mathcal{A}|\cdot |\mathcal{B}|)}\right)}$, where $\mathcal{A}$ and $\mathcal{B}$ represent the sets from which the answers of Alice and Bob are drawn.

14 pages. Accepted by CCC 2014, camera-ready version

References in corpus (7)

• Secure device-independent quantum key distribution with causally independent measurement devices
• A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography
• Device-Independent Quantum Key Distribution with Commuting Measurements
• Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity
• Analytical Approach to Parallel Repetition
• A parallel repetition theorem for entangled projection games
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

Cited by in corpus (2)

• A parallel repetition theorem for entangled projection games
• Parallel repetition via fortification: analytic view and the quantum case