Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-060 | 15th April 2016 04:57

A parallel repetition theorem for all entangled games


Authors: Henry Yuen
Publication: 15th April 2016 12:25
Downloads: 297


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} \log n$ 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.

ISSN 1433-8092 | Imprint