Quantum XOR games

Oded Regev, Thomas Vidick

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013
Number of pages12
StatePublished - 2013
Event2013 IEEE Conference on Computational Complexity, CCC 2013 - Palo Alto, CA, United States
Duration: Jun 5 2013Jun 7 2013

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159


Other2013 IEEE Conference on Computational Complexity, CCC 2013
Country/TerritoryUnited States
CityPalo Alto, CA


  • Grothendieck inequality
  • XOR games
  • quantum games
  • semidefinite programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


Dive into the research topics of 'Quantum XOR games'. Together they form a unique fingerprint.

Cite this