Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Quantum XOR Games

Quantum XOR Games Quantum XOR Games ´ ODED REGEV, CNRS, D´ partement d'Informatique, Ecole normale sup´ rieure, Paris e e THOMAS VIDICK, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology 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. Categories and Subject Descriptors: F.1.2. [Modes of Computation]: http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Quantum XOR Games

Download PDF
43 pages

Loading next page...
 
/lp/association-for-computing-machinery/quantum-xor-games-ze3inf0D7V
Publisher
Association for Computing Machinery
Copyright
Copyright © 2015 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2799560
Publisher site
See Article on Publisher Site

Abstract

Quantum XOR Games ´ ODED REGEV, CNRS, D´ partement d'Informatique, Ecole normale sup´ rieure, Paris e e THOMAS VIDICK, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology 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. Categories and Subject Descriptors: F.1.2. [Modes of Computation]:

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Aug 31, 2015

There are no references for this article.