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

DOI10.1137/140956622zbMath1342.81080arXiv1302.1242OpenAlexW2466331000WikidataQ59792576 ScholiaQ59792576MaRDI QIDQ2816299

Thomas Vidick

Publication date: 4 July 2016

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

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

zbMATH Keywords

PCP theoremBell inequalitiesentangled gamesXOR games

Mathematics Subject Classification ID

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

Related Items (9)

Quantum de Finetti theorems under local measurements with applications ⋮ Interactive Proofs with Approximately Commuting Provers ⋮ Geometry of information structures, strategic measures and associated stochastic control topologies ⋮ A formalization of the CHSH inequality and Tsirelson's upper-bound in Isabelle/HOL ⋮ Unnamed Item ⋮ Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate ⋮ Unnamed Item ⋮ A parallel repetition theorem for entangled projection games ⋮ Rank-one quantum games

Cites Work

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

This page was built for publication: Three-Player Entangled XOR Games are NP-Hard to Approximate