Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

摘要

In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω~*(G) of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The n-fold parallel repetition G~n of G consists of n instances of G where the players receive all the inputs at the same time and produce all the outputs at the same time. They win G~n if they win each instance of G. In this paper we show that for any game G such that ω~*(G) = 1 - ε ＜ 1, ω~*(G~n) decreases exponentially in n. First, for any game G on the uniform distribution, we show that ω~*(G~n) = (1 - ε~2)~(Ω(n/log(|I||O|)-|log(ε)|)), where |I| and |O| are the sizes of the input and output sets. From this result, we show that for any entangled game G, ω~*(G~n) = (1 -ε~2)~(Ω(n/Q~4 log(Q•|O|)-|log(ε/Q)|)) where p is the input distribution of G and Q=max(「1/min_(xy:pxy≠0{(pxy)~(1/2)}],|I|). To prove this parallel repetition, we introduce the concept of Superposed Information Cost for entangled games which is inspired from the information cost used in communication complexity.