A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions
Rahul Jain, Attila Pereszlényi, Penghui Yao · 2014
We show a parallel repetition theorem for the entangled value ω*(G) of any two-player one-round game G where the questions (x, y) ∈ X × Y to Alice and Bob are drawn from a product distribution on X × Y. We show that for the k-fold product Gkof the game G (which represents the game G played in parallel k times independently) ω*(Gk) = (1 - (1 - ω*(G))3)Ω(k/Iog(|A|·|B|)where A and B represent the sets from which the answers of Alice and Bob are drawn. The arguments we use are information theoretic and are broadly on similar lines as that of Raz [1] and Holenstein [2] for classical games. The additional quantum ingredients we need, to deal with entangled games, are inspired by the work of Jain, Radhakrishnan, and Sen [3], where quantum information theoretic arguments were used to achieve message compression in quantum communication protocols.