TY - GEN
T1 - Quantum strategies are better than classical in almost any XOR game
AU - Ambainis, Andris
AU - Bačkurs, Arturs
AU - Balodis, Kaspars
AU - Kravčenko, Dmitrijs
AU - Ozols, Raitis
AU - Smotrovs, Juris
AU - Virza, Madars
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84873844360
U2 - 10.1007/978-3-642-31594-7_3
DO - 10.1007/978-3-642-31594-7_3
M3 - Conference paper
AN - SCOPUS:84873844360
SN - 9783642315930
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 25
EP - 37
BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Y2 - 9 July 2012 through 13 July 2012
ER -