Entanglement of approximate quantum strategies in XOR games

Abstract

We show that for any $\epsilon >0$ there is an XOR game $G=G(\epsilon )$ with $\Theta ({\epsilon }^{-1/5})$ inputs for one player and $\Theta ({\epsilon }^{-2/5})$ inputs for the other player such that $\Omega ({\epsilon }^{-1/5})$ ebits are required for any strategy achieving bias that is at least a multiplicative factor $(1-\epsilon )$ from optimal. This gives an exponential improvement in both the number of inputs or outputs and the noise tolerance of any previously-known self-test for highly entangled states. Up to the exponent $-1/5$ the scaling of our bound with $\epsilon$ is tight: for any XOR game there is an $\epsilon$-optimal strategy using $\lceil {\epsilon }^{-1}\rceil$ ebits, irrespective of the number of questions in the game.