Quantum strategies are better than classical in almost any XOR game

Andris Ambainis, Arturs Backurs, Kaspars Balodis +4

We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n,…