Entanglement of approximate quantum strategies in XOR games

Abstract

We show that for any ε > 0 there is an XOR game G = G(ε) with Θ(ε^(−1/5)) inputs for one player and Θ(ε^(−2/5)) inputs for the other player such that Ω(ε^(−1/5)) ebits are required for any strategy achieving bias that is at least a multiplicative factor (1−ε) 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 ε is tight: for any XOR game there is an ε-optimal strategy using ⌈ε^(−1)⌉ ebits, irrespective of the number of questions in the game.