Anchored parallel repetition for nonlocal games

DOI10.1137/21M1405927MaRDI QIDQ5067446zbMATHOpenAlexFDO

Authors Mohammad Bavarian, Thomas Vidick, Henry C. Yuen

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6829293 (Why is no real title available?)
• scientific article; zbMATH DE number 5937160 (Why is no real title available?)
• A Parallel Repetition Theorem
• A counterexample to strong parallel repetition
• A parallel repetition theorem for all entangled games
• A parallel repetition theorem for entangled projection games
• Analytical approach to parallel repetition
• Certifiable quantum dice
• Error reduction by parallel repetition - a negative result
• Hardness amplification for entangled games via anchoring
• Multiplayer parallel repetition for expanding games
• On the distributional complexity of disjointness
• On the power of multi-prover interactive protocols
• On the power of unique 2-prover 1-round games
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• Parallel repetition in projection games and a concentration bound
• Parallel repetition of entangled games
• Parallel repetition via fortification: analytic view and the quantum case
• Parallel repetition: simplification and the no-signaling case
• Perfect parallel repetition theorem for quantum XOR proof systems
• Proposed experiment to test local hidden-variable theories
• Quantum information theory
• Simple unified form for the major no-hidden-variables theorems
• Strong Parallel Repetition Theorem for Free Projection Games
• The set of quantum correlations is not closed
• Two-Prover Protocols---Low Error at Affordable Rates
• Unique games with entangled provers are easy

Cited in

(4)

• Parallel repetition of entangled games
• Parallel repetition via fortification: analytic view and the quantum case
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• Hardness amplification for entangled games via anchoring

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)