Three-Player Entangled XOR Games are NP-Hard to Approximate
From MaRDI portal
Publication:2816299
DOI10.1137/140956622zbMath1342.81080arXiv1302.1242OpenAlexW2466331000WikidataQ59792576 ScholiaQ59792576MaRDI QIDQ2816299
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
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
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?
