[en] non-local XOR games ; entanglement ; nearly-optimal strategies
[en] We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game $G$ and $\eps>0$ there is an $\eps$-optimal strategy for $G$ using $\lceil \eps^{-1} \rceil$ ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH($n$) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any $\eps>0$ there is an $n = \Theta(\eps^{-1/5})$ such that $\Omega(\eps^{-1/5})$ ebits are required for any strategy achieving bias that is at least a multiplicative factor $(1-\eps)$ from optimal in CHSH($n$).
[University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
