Anchored parallel repetition for nonlocal games

DOI10.1137/21M1405927zbMATH Open1483.68136arXiv1509.07466OpenAlexW3135158295MaRDI QIDQ5067446FDOQ5067446

Authors: Mohammad Bavarian, Thomas Vidick, Henry C. Yuen 

Publication date: 1 April 2022

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

Abstract: We introduce a simple transformation on two-player nonlocal games, called "anchoring", and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige-Kilian transformation (SICOMP 2000), and has the property that if the quantum value of the original game $G$ is $v$ then the quantum value of the anchored game $$ is $1-(1-alpha{)}^{2}cdot(1-v)$ where $alpha$ is a parameter of the transformation. In particular the anchored game has quantum value $1$ if and only if the original game $G$ has quantum value $1$. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.

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

Recommendations

• Hardness amplification for entangled games via anchoring
• Parallel repetition of entangled games
• A parallel repetition theorem for entangled projection games
• A parallel repetition theorem for all entangled games
• Parallel repetition via fortification: analytic view and the quantum case

zbMATH Keywords

quantum informationparallel repetitionhardness amplificationnonlocal gamesgap amplificationquantum complexity theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) 2-person games (91A05) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cites Work

• Proposed experiment to test local hidden-variable theories
• Simple unified form for the major no-hidden-variables theorems
• Quantum information theory
• On the power of unique 2-prover 1-round games
• Certifiable quantum dice
• A Parallel Repetition Theorem
• Analytical approach to parallel repetition
• On the distributional complexity of disjointness
• Parallel repetition: simplification and the no-signaling case
• Unique games with entangled provers are easy
• On the power of multi-prover interactive protocols
• Error reduction by parallel repetition - a negative result
• Parallel repetition in projection games and a concentration bound
• Strong Parallel Repetition Theorem for Free Projection Games
• Title not available (Why is that?)
• A parallel repetition theorem for entangled projection games
• Perfect parallel repetition theorem for quantum XOR proof systems
• Two-Prover Protocols---Low Error at Affordable Rates
• THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED
• Parallel repetition of entangled games
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• A counterexample to strong parallel repetition
• A parallel repetition theorem for all entangled games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hardness amplification for entangled games via anchoring

Cited In (3)

• Parallel repetition of entangled games
• Hardness amplification for entangled games via anchoring
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

This page was built for publication: Anchored parallel repetition for nonlocal games

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