6533b872fe1ef96bd12d2e75

RESEARCH PRODUCT

Quantum strategies are better than classical in almost any XOR game

Andris AmbainisArturs BackursKaspars BalodisDmitry KravcenkoRaitis OzolsJuris SmotrovsMadars Virza

subject

FOS: Computer and information sciencesQuantum PhysicsComputer Science - Computer Science and Game TheoryFOS: Physical sciencesQuantum Physics (quant-ph)Computer Science and Game Theory (cs.GT)

description

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.

yearjournalcountryeditionlanguage
2011-12-14
http://arxiv.org/abs/1112.3330