[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$).
Disciplines :
Physics
Author, co-author :
OSTREV, Dimiter ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Vidick, Thomas; California Institute of Technology - CALTECH > Department of Computing and Mathematical Sciences
External co-authors :
yes
Language :
English
Title :
Entanglement of Approximate Quantum Strategies in XOR Games