Quantum strategies are better than classical in almost any XOR game
arXiv:1112.3330
Abstract
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.
arXiv comment22 pages, 1 figure
References in corpus (6)
- Guess your neighbour's input: a multipartite non-local game with no quantum advantage
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- Large violation of Bell inequalities with low entanglement
- Fully Distrustful Quantum Cryptography
- Error Bounds for Random Matrix Approximation Schemes
- Gamma-rays as a diagnostic of the origin of core radiation in low-luminosity active galactic nuclei