A Caltech Library Service

Quantum XOR Games

Regev, Oded and Vidick, Thomas (2015) Quantum XOR Games. ACM Transactions on Computation Theory, 7 (4). Art. No. 15. ISSN 1942-3454. doi:10.1145/2799560.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck’s inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance that players can obtain in a given game, both in the case that they have no shared entanglement and that they share unlimited entanglement. As a byproduct of the algorithm, we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2015 ACM. Received February 2013; revised May 2015; accepted May 2015. Oded Regev’s research was supported by a European Research Council (ERC) Starting Grant. Thomas Vidick was supported by the National Science Foundation under Grant No. 0844626. We are grateful to David Pérez-García for suggesting the family of games (T_n). We also thank him and Carlos Palazuelos for many useful discussions, and the anonymous referees for many useful comments.
Funding AgencyGrant Number
European Research Council (ERC)UNSPECIFIED
Subject Keywords:XOR games, entangled games, Grothendieck inequality
Issue or Number:4
Record Number:CaltechAUTHORS:20160321-083901879
Persistent URL:
Official Citation:Oded Regev and Thomas Vidick. 2015. Quantum XOR games. ACM Trans. Comput. Theory 7, 4, Article 15 (August 2015), 43 pages. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65508
Deposited By: Ruth Sustaita
Deposited On:29 Mar 2016 22:51
Last Modified:10 Nov 2021 23:46

Repository Staff Only: item control page