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

Abstract

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.

The paper has been withdrawn due to an error in the proof of the main theorem. For details, see http://users.cms.caltech.edu/~vidick/errata.pdf

Cited by in corpus (12)

• Robust self-testing of many-qubit states
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• The Quantum PCP Conjecture
• Binary Constraint System Games and Locally Commutative Reductions
• Extended nonlocal games and monogamy-of-entanglement games
• Limitations of semidefinite programs for separable states and entangled games
• A parallel repetition theorem for entangled projection games
• Parallel repetition via fortification: analytic view and the quantum case
• Constant-Soundness Interactive Proofs for Local Hamiltonians
• A multiprover interactive proof system for the local Hamiltonian problem
• Extended Nonlocal Games
• Interactive proofs with approximately commuting provers