A Caltech Library Service

Quantum XOR Games

Regev, Oded and Vidick, Thomas (2013) Quantum XOR Games. In: 28th Annual IEEE Conference on Computational Complexity (CCC). IEEE , Piscataway, NJ, pp. 144-155. ISBN 978-0-7695-4997-2.

[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 players can obtain in a given game, both in case they have no shared entanglement and in case 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:Book Section
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2013 IEEE.
Subject Keywords:XOR games; entangled games; Grothendieck inequality
Record Number:CaltechAUTHORS:20160329-155246836
Persistent URL:
Official Citation:O. Regev and T. Vidick, "Quantum XOR Games," Computational Complexity (CCC), 2013 IEEE Conference on, Stanford, CA, 2013, pp. 144-155. doi: 10.1109/CCC.2013.23
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65753
Deposited By: Tony Diaz
Deposited On:30 Mar 2016 19:09
Last Modified:10 Nov 2021 23:49

Repository Staff Only: item control page