A Caltech Library Service

Entangled Games Are Hard to Approximate

Kempe, Julia and Kobayashi, Hirotada and Matsumoto, Keiji and Toner, Ben and Vidick, Thomas (2011) Entangled Games Are Hard to Approximate. SIAM Journal on Computing, 40 (3). pp. 848-877. ISSN 0097-5397. doi:10.1137/090751293.

PDF - Published 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 verifier and a team of provers 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) a quantum verifier and two entangled provers or (ii) a classical verifier and three entangled provers. 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 of entangled-prover games to within a constant. Using our techniques we also show that every language in PSPACE has a two-prover one-round interactive proof system with perfect completeness and soundness 1-1/poly even against entangled provers. We start our proof by describing two ways to modify classical multiprover games to make them resistant to entangled provers. 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-prover games cannot be computed by semidefinite programs that are polynomial in the size of the verifier's system, a method that has been successful for more restricted quantum games.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2011 Society for Industrial and Applied Mathematics. Received March 02, 2009; Accepted October 01, 2010; Published online June 23, 2011. 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. This author’s work was partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as contract 015848, by an Alon Fellowship of the Israeli Higher Council of Academic Research, by a grant of the Israeli Science Foundation, by an ERC Starting Researcher grant, and by a grant from the Wolfson Family Charitable Trust. Support by Michel Cukierman is also gratefully acknowledged. The work of these authors was supported by the Strategic Information and Communications R&D Promotion Programme 031303020 of the Ministry of Internal Affairs and Communications of Japan. This author’s work was 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. This author’s work was supported by ARO grant W911NF-09-1-0440 and NSF grant CCF-0905626.
Funding AgencyGrant Number
European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorateUNSPECIFIED
Israeli Higher Council of Academic Research Alon FellowshipUNSPECIFIED
Israel Science FoundationUNSPECIFIED
European Research Council (ERC)UNSPECIFIED
Wolfson Family Charitable TrustUNSPECIFIED
Strategic Information and Communications R&D Promotion Programme 031303020 of the Ministry of Internal Affairs and Communications of JapanUNSPECIFIED
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)639-023-302
Army Research Office (ARO)W911NF-09-1-0440
Subject Keywords:interactive proofs; quantum computing; entanglement; almost-commuting matrices
Issue or Number:3
Classification Code:AMS Subject Headings: 81P68, 68Q10
Record Number:CaltechAUTHORS:20110713-155400829
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24413
Deposited On:14 Jul 2011 14:46
Last Modified:09 Nov 2021 16:23

Repository Staff Only: item control page