Anchored Parallel Repetition for Nonlocal Games
DOI10.1137/21M1405927zbMath1483.68136arXiv1509.07466OpenAlexW3135158295MaRDI QIDQ5067446
Henry C. Yuen, Mohammad Bavarian, Thomas Vidick
Publication date: 1 April 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.07466
hardness amplificationquantum informationparallel repetitionnonlocal gamesgap amplificationquantum complexity theory
2-person games (91A05) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Perfect parallel repetition theorem for quantum XOR proof systems
- On the distributional complexity of disjointness
- On the power of multi-prover interactive protocols
- Error reduction by parallel repetition - a negative result
- A parallel repetition theorem for entangled projection games
- Certifiable quantum dice
- A Counterexample to Strong Parallel Repetition
- Parallel Repetition in Projection Games and a Concentration Bound
- On the power of unique 2-prover 1-round games
- Strong Parallel Repetition Theorem for Free Projection Games
- A Parallel Repetition Theorem
- Simple unified form for the major no-hidden-variables theorems
- Two-Prover Protocols---Low Error at Affordable Rates
- A parallel repetition theorem for all entangled games
- THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED
- Hardness amplification for entangled games via anchoring
- Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
- Analytical approach to parallel repetition
- Proposed Experiment to Test Local Hidden-Variable Theories
- Unique Games with Entangled Provers Are Easy
- Parallel repetition of entangled games
- Quantum Information Theory
This page was built for publication: Anchored Parallel Repetition for Nonlocal Games