scientific article; zbMATH DE number 7250160

DOI10.4230/LIPICS.CCC.2018.20MaRDI QIDQ5121908zbMATH OpenFDO

Authors Anand Natarajan, Thomas Vidick

Publication date 22 September 2020

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

zbMATH Keywords

multi-prover interactive proof systemslow-degree testingentangled nonlocal games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68) 2-person games (91A05)

Recommendations

• Entangled games are hard to approximate
• Three-player entangled XOR games are NP-hard to approximate
• Unique games with entangled provers are easy
• Parallel repetition of entangled games
• Quantum XOR games

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)
• A parallel repetition theorem for entangled projection games
• A quantum linearity test for robustly verifying entanglement
• Algebraic methods for interactive proof systems
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Classical verification of quantum proofs
• Delegating computation: interactive proofs for muggles
• How to delegate computations
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• Monogamy of non-local quantum correlations
• Non-deterministic exponential time has two-prover interactive protocols
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Self-testing/correcting with applications to numerical problems
• Some optimal inapproximability results

Cited in

(11)

• Unique games with entangled provers are easy
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• scientific article; zbMATH DE number 7559053 (Why is no real title available?)
• Entangled games are hard to approximate
• Hardness amplification for entangled games via anchoring
• Characterization of binary constraint system games
• Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
• Geometry of information structures, strategic measures and associated stochastic control topologies
• Three-player entangled XOR games are NP-hard to approximate
• Quantum free games
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)

This page was built for publication:

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