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 ε⁻¹ ebits, irrespective of the number of questions in the game.
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).