Quantum strategies for simple two-player XOR games

Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs +1 more

Andris Ambainis, Jānis Iraids, Dmitry Kravchenko +1 more

Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis +4 more

Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis +4 more

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, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form $\sum_i \alpha_i \ket{i}\cdots\ket{i}$ for arbitrary amplitudes $\alpha_i$. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Marius Junge, Carlos Palazuelos, Ignacio Villanueva