6533b7dcfe1ef96bd127331f
RESEARCH PRODUCT
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
Andris AmbainisKaspars BalodisArturs BackursRaitis OzolsMadars VirzaJuris SmotrovsDmitrijs Kravčenkosubject
Discrete mathematicsQuantum pseudo-telepathy010102 general mathematics0103 physical sciencesFraction (mathematics)0101 mathematics010306 general physics01 natural sciencesValue (mathematics)QuantumMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-01-01 |