Entangled games are hard to approximate

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)848-877
Number of pages30
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2011


  • Almost-commuting matrices
  • Entanglement
  • Interactive proofs
  • Quantum computing

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Entangled games are hard to approximate'. Together they form a unique fingerprint.

Cite this