A Caltech Library Service

Entangled games are hard to approximate

Kempe, Julia and Kobayashi, Hirotada and Matsumoto, Keiji and Toner, Ben and Vidick, Thomas (2008) Entangled games are hard to approximate. In: 49th Annual Symposium on Foundations-of-Computer-Science (FOCS). IEEE Computer Society , Los Alamitos, CA, pp. 447-456. ISBN 978-0-7695-3436-7.

PDF - Published Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We establish the first hardness results for the problem of computing the value of one-round games played by a referee and a team of players who can share quantum entanglement. In particular, we show that it is NP-hard to approximate within an inverse polynomial the value of a one-round game with (i) quantum referee and two entangled players or (ii) classical referee and three entangled players. Previously it was not even known if computing the value exactly is NP-hard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation to within a constant.We start our proof by describing two ways to modify classical multi-player games to make them resistant to entangled players. We then show that a strategy for the modified game that uses entanglement can be "rounded'' to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless P = NP, the values of entangled-player games cannot be computed by semidefinite programs that are polynomial in the size of the referee's system, a method that has been successful for more restricted quantum games.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2008 IEEE. Work partly done while at LRI, Univ. de Paris-Sud, Orsay. Supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848, by an Alon Fellowship of the Israeli Higher Council of Academic Research, by a grant of the Israeli Science Foundation and by a European Research Council (ERC) Starting Grant. Supported by the Strategic Information and Communications R&D Promotion Programme No. 031303020 of the Ministry of Internal Affairs and Communications of Japan. Part of this work was completed at Caltech. Supported by the National Science Foundation under Grants PHY-0456720 and CCF-0524828, by EU project QAP, by NWO VICI project 639-023-302, and by the Dutch BSIK/BRICKS project. Work partly done while at LRI, Univ. de Paris-Sud, Orsay, and at DI, École Normale Supérieure, Paris, France. We thank Tsuyoshi Ito, Jaikumar Radhakrishnan, Oded Regev, Amnon Ta-Shma, Mario Szegedy and Andy Yao for helpful discussions and John Watrous for pointing out that the optimal quantum value of a game might not be achievable with finite dimensional entanglement.
Funding AgencyGrant Number
European Research Council (ERC)015848
Israeli Higher Council of Academic Research Alon FellowshipUNSPECIFIED
Israel Science FoundationUNSPECIFIED
Ministry of Internal Affairs and Communications of Japan Strategic Information and Communications R&D Promotion Programme031303020
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)639-023-302
Record Number:CaltechAUTHORS:20140910-085511133
Persistent URL:
Official Citation:Kempe, J.; Kobayashi, H.; Matsumoto, K.; Toner, B.; Vidick, T., "Entangled Games are Hard to Approximate," Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on , vol., no., pp.447,456, 25-28 Oct. 2008 doi: 10.1109/FOCS.2008.8
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49521
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 19:55
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page