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

2013/02/06 by Thomas Vidick, Vidick, Thomas · 8 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1302.1242

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

openalex publication_date 2013/02/06 · arxiv created 2020/11/13 · arxiv updated 2020/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ≠ 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.

Citations

• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Discussion of Probability Relations between Separated Systems
• On the Einstein Podolsky Rosen paradox
• A multi-prover interactive proof for NEXP sound against entangled provers

Cited by

• The NPA hierarchy does not always attain the commuting operator value
• Approximating the quantum value of an LCS game is RE-hard
• A parallel repetition theorem for entangled projection games
• Gap-preserving reductions and RE-completeness of independent set games
• A multiprover interactive proof system for the local Hamiltonian problem
• Quantum soundness of the classical low individual degree test
• Two-player entangled games are NP-hard
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA

Related

• Entangled games are hard to approximate
• On the Power of Entangled Quantum Provers
• Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
• Entanglement of approximate quantum strategies in XOR games
• On the power of quantum entanglement in multipartite quantum XOR games