Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0704.2903 · SIAM Journal on Computing

Entangled Games Are Hard to Approximate

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

Published Jan 1, 2011• 74 citations
arXivHTMLPDF

Abstract

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/\,\mathrm{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 $\mathrm{P}=\mathrm{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.

DOI
10.1137/090751293

Related papers

Entangled Games are Hard to Approximate

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +2 more

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•56 citations

Unique Games with Entangled Provers are Easy

Julia Kempe, Oded Regev, Ben Toner

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers. Using our approximation by a semidefinite program we also show a parallel repetition theorem for unique entangled games.

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•42 citations

On the Power of Entangled Quantum Provers

Julia Kempe, Thomas Vidick

We show that the value of a general two-prover quantum game cannot be computed by a semi-definite program ofvpolynomial size (unless P=NP), a method that has been successful in more restricted quantum games. More precisely, we show that proof of membership in the NP-complete problem GAP-3D-Matching can be obtained by a 2-prover, 1-round quantum interactive proof system where the provers share entanglement, with perfect completeness and soundness s=1-2^(-O(n)), and such that the space of the verifier and the size of the messages are O(log n). This implies that QMIP^*_{log n,1,1-2^(-O(n))} \nsubseteq P unless P = NP and provides the first non-trivial lower bound on the power of entangled quantum provers, albeit with an exponentially small gap. The gap achievable by our proof system might in fact be larger, provided a certain conjecture on almost commuting versus nearly commuting projector matrices is true.

arXiv:quant-ph/0612063•Dec 8, 2006•9 citations

Unique Games with Entangled Provers Are Easy

Julia Kempe, Oded Regev, Ben Toner

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are “unique” constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel “quantum rounding technique,” showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games.

arXiv:0710.0655•SIAM Journal on Computing•Jan 1, 2010•86 citations

The Unique Games Conjecture with Entangled Provers is False

Julia Kempe, Oded Regev, Ben Toner

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers.

Dagstuhl Seminar Proceedings•Jan 1, 2008•6 citations

On the Power of Entangled Provers: Immunizing games against entanglement

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +2 more

We describe two generic ways to make multi-prover classical games resistant against entangled provers. The first uses quantum communication and a quantum verifier, the second adds an additional prover. This leads to several new results on the power of proof systems with entangled provers. We show that NEXP ⊆ QMIP1,s(2, 1) and NEXP ⊆ MIP1,s(3, 1) with soundness s = 1− 2− poly(n) and PSPACE ⊆ MIP1,s(2, 1) with soundness s = 1 − 1/ poly(n), providing the first non-trivial bounds in this setting. Moreover, our results imply that, unless P = NP, the value of entangled prover games cannot be computed by semi-definite programs that are polynomial in the size of the verifier’s system, a method that has been successful for more restricted quantum games. ∗also at CNRS & LRI, Univerite de Paris-Sud, Orsay, France †Partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848 and by an Alon Fellowship of the Israeli Higher Council of Academic Research. ‡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, and by NWO VICI project 639-023-302. Part of this research has been funded by the Dutch BSIK/BRICKS project. §Work partly done while at LRI, Univ. de Paris-Sud, Orsay.

•Apr 23, 2007•10 citations
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/ poly1-1/\,\mathrm{poly}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\mathrm{P}=\mathrm{NP}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.
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.
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers. Using our approximation by a semidefinite program we also show a parallel repetition theorem for unique entangled games.
We show that the value of a general two-prover quantum game cannot be computed by a semi-definite program ofvpolynomial size (unless P=NP), a method that has been successful in more restricted quantum games. More precisely, we show that proof of membership in the NP-complete problem GAP-3D-Matching can be obtained by a 2-prover, 1-round quantum interactive proof system where the provers share entanglement, with perfect completeness and soundness s=1-2^(-O(n)), and such that the space of the verifier and the size of the messages are O(log n). This implies that QMIP^*_{log n,1,1-2^(-O(n))} \nsubseteq P unless P = NP and provides the first non-trivial lower bound on the power of entangled quantum provers, albeit with an exponentially small gap. The gap achievable by our proof system might in fact be larger, provided a certain conjecture on almost commuting versus nearly commuting projector matrices is true.
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are “unique” constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel “quantum rounding technique,” showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games.
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers.
We describe two generic ways to make multi-prover classical games resistant against entangled provers. The first uses quantum communication and a quantum verifier, the second adds an additional prover. This leads to several new results on the power of proof systems with entangled provers. We show that NEXP ⊆ QMIP1,s(2, 1) and NEXP ⊆ MIP1,s(3, 1) with soundness s = 1− 2− poly(n) and PSPACE ⊆ MIP1,s(2, 1) with soundness s = 1 − 1/ poly(n), providing the first non-trivial bounds in this setting. Moreover, our results imply that, unless P = NP, the value of entangled prover games cannot be computed by semi-definite programs that are polynomial in the size of the verifier’s system, a method that has been successful for more restricted quantum games. ∗also at CNRS & LRI, Univerite de Paris-Sud, Orsay, France †Partially supported by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848 and by an Alon Fellowship of the Israeli Higher Council of Academic Research. ‡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, and by NWO VICI project 639-023-302. Part of this research has been funded by the Dutch BSIK/BRICKS project. §Work partly done while at LRI, Univ. de Paris-Sud, Orsay.