부산대학교 도서관

We show a parallel repetition theorem for the entangled value omega*(G) of any two-player one-round game G where the questions (x, y) in X x Y to Alice and Bob are drawn from a product distribution on X x Y. We show that for the k-fold product G^k of the game G (which represents the game G played in parallel k times independently) omega*(G^k) = (1 - (1 - omega*(G))^3)^Omega(k / log(|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 [1995] and Holenstein [2007] for classical games. The additional quantum ingredients we need, to deal with entangled games, are inspired by the work of Jain, Radhakrishnan, and Sen [2008], where quantum information theoretic arguments were used to achieve message compression in quantum communication protocols.