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

SIAM Journal on Computing

Three-Player Entangled XOR Games are NP-Hard to Approximate

Thomas Vidick

Published Jan 1, 2016• 20 citations
Publisher

Abstract

We show that for any $\varepsilon>0$ the problem of finding a factor $(2-\varepsilon)$ approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P$\neq$NP. They can be thought of as an extension of H\aastad's optimal hardness of approximation results for MAX-E3-LIN2 [J. ACM, 48 (2001), pp. 798--859] to the entangled-player setting. The key technical component of our work is a soundness analysis of a plane-vs-point low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick [Proceedings of the $53$rd FOCS, IEEE, Piscataway, NJ, 2012, pp. 243--252]. Our results demonstrate the possibility of efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.

DOI
10.1137/140956622

Related papers

Three-player entangled XOR games are NP-hard to approximate

Thomas Vidick

We show that for any eps>0 the problem of finding a factor (2-eps) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P \neq NP. They can be thought of as an extension of Hastad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.

arXiv:1302.1242•Feb 6, 2013•33 citations

Two-player entangled games are NP-hard

Anand Natarajan, Thomas Vidick

We show that the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length is NP-hard to approximate to within constant factors. As a corollary, the inclusion $\mathrm{NEXP}\subseteq\mathrm{MIP}^*$, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.

arXiv:1710.03062•Oct 9, 2017•7 citations

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•55 citations

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form $\sum_i \alpha_i \ket{i}\cdots\ket{i}$ for arbitrary amplitudes $\alpha_i$. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information and Computation•Mar 1, 2013•17 citations

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information Processing•Mar 1, 2013•1 citation

XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

Richard Cleve, Eric Culf, Aviv Taller

It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

quant-pharXiv:2607.06876•Jul 9, 2026•0 citations
We show that for any ε>0\varepsilon>0ε>0 the problem of finding a factor (2−ε)(2-\varepsilon)(2−ε) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P≠\neq=NP. They can be thought of as an extension of H\aastad's optimal hardness of approximation results for MAX-E3-LIN2 [J. ACM, 48 (2001), pp. 798--859] to the entangled-player setting. The key technical component of our work is a soundness analysis of a plane-vs-point low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick [Proceedings of the 535353rd FOCS, IEEE, Piscataway, NJ, 2012, pp. 243--252]. Our results demonstrate the possibility of efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
We show that for any eps>0 the problem of finding a factor (2-eps) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P \neq NP. They can be thought of as an extension of Hastad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
We show that the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length is NP-hard to approximate to within constant factors. As a corollary, the inclusion NEXP⊆MIP∗\mathrm{NEXP}\subseteq\mathrm{MIP}^*NEXP⊆MIP∗, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.
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 study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form ∑iαi∣i⟩⋯∣i⟩\sum_i \alpha_i \ket{i}\cdots\ket{i}∑i​αi​∣i⟩⋯∣i⟩ for arbitrary amplitudes αi\alpha_iαi​. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.