Quantum strategies are better than classical in almost any XOR game

Andris Ambainis; Arturs Backurs; Dmitry Kravcenko; Juris Smotrovs; Kaspars Balodis; Madars Virza; Raitis Ozols

REVIEW

Quantum strategies are better than classical in almost any XOR game

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1112.3330 v1 pith:MZROEPXU submitted 2011-12-14 quant-ph cs.GT

Andris Ambainis , Arturs Backurs , Kaspars Balodis , Dmitry Kravcenko , Raitis Ozols , Juris Smotrovs , Madars Virza This is my paper

classification quant-phcs.GT

keywords playerclassicalgamealmostbettergamesquantumrandom

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original 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.

Discussion (0). Sign in to comment.

Pith tools