A parallel repetition theorem for all entangled games

DOI10.4230/LIPICS.ICALP.2016.77MaRDI QIDQ4598217zbMATH OpenOpenAlexFDO

Authors Henry C. Yuen

Publication date 19 December 2017

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

zbMATH Keywords

direct product theoremsentangled gamesparallel repetitionquantum games

Mathematics Subject Classification ID

Quantum coherence, entanglement, quantum correlations (81P40) Multistage and repeated games (91A20)

Abstract: The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known. We prove that the entangled value of a two-player game $G$ repeated $n$ times in parallel is at most $c_G{n}^{-1/4}logn$ for a constant $c_G$ depending on $G$, provided that the entangled value of $G$ is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.

Recommendations

• A parallel repetition theorem for entangled projection games
• Parallel repetition of entangled games
• scientific article; zbMATH DE number 6829293
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• Hardness amplification for entangled games via anchoring

Cited in

(13)

• A parallel repetition theorem for entangled projection games
• Strong Parallel Repetition Theorem for Free Projection Games
• scientific article; zbMATH DE number 6829293 (Why is no real title available?)
• Multiplayer parallel repetition for expanding games
• Information value of two-prover games
• scientific article; zbMATH DE number 7375938 (Why is no real title available?)
• Anchored parallel repetition for nonlocal games
• The Hilbertian tensor norm and entangled two-prover games
• Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• Unique games with entangled provers are easy
• Parallel repetition of entangled games
• A direct product theorem for quantum communication complexity with applications to device-independent cryptography
• On approximate reconfigurability of label cover

This page was built for publication: A parallel repetition theorem for all entangled games

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