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

DOI10.1137/140956622zbMATH Open1342.81080arXiv1302.1242OpenAlexW2466331000WikidataQ59792576 ScholiaQ59792576MaRDI QIDQ2816299FDOQ2816299

Authors: Thomas Vidick 

Publication date: 4 July 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1302.1242

Recommendations

• Entangled games are hard to approximate
• scientific article; zbMATH DE number 7250160
• Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games
• Hardness amplification for entangled games via anchoring

zbMATH Keywords

entangled gamesBell inequalitiesPCP theoremXOR games

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Quantum computation (81P68) Quantum measurement theory, state operations, state preparations (81P15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) (n)-person games, (n>2) (91A06)

Cites Work

• Computational Complexity
• Proposed experiment to test local hidden-variable theories
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Interactive proofs and the hardness of approximating cliques
• Title not available (Why is that?)
• Some optimal inapproximability results
• Self-testing/correcting with applications to numerical problems
• The knowledge complexity of interactive proof-systems
• Title not available (Why is that?)
• Robust Characterizations of Polynomials with Applications to Program Testing
• Quantum de finetti theorems under local measurements with applications
• Non-deterministic exponential time has two-prover interactive protocols
• A Parallel Repetition Theorem
• Efficient probabilistically checkable proofs and applications to approximations
• Unique games with entangled provers are easy
• Entangled games are hard to approximate
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Title not available (Why is that?)
• A parallel repetition theorem for entangled projection games
• Sub-constant error probabilistically checkable proof of almost-linear size
• PCP characterizations of NP: toward a polynomially-small error-probability
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Delegation for bounded space
• Parallel repetition of entangled games
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

Cited In (11)

• Quantum de Finetti theorems under local measurements with applications
• Title not available (Why is that?)
• Rank-one quantum games
• Entangled games are hard to approximate
• A parallel repetition theorem for entangled projection games
• Hardness amplification for entangled games via anchoring
• Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
• A formalization of the CHSH inequality and Tsirelson's upper-bound in Isabelle/HOL
• Geometry of information structures, strategic measures and associated stochastic control topologies
• Interactive proofs with approximately commuting provers
• Parallel repetition via fortification: analytic view and the quantum case

This page was built for publication: Three-player entangled XOR games are NP-hard to approximate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2816299)