Thomas Vidick, University of California, Berkeley
Abstract
Suppose that a referee interacts with two entangled players, Alice and
Bob, through a one-round game with classical communication. We have a
promise that one of two cases hold: either the players can win the
game with certainty, or they have at least a 1% chance of getting
caught. The referee would like to determine which is the case, with
high confidence. Note that if he plays the game only once, then in
both cases it is likely that the players will succeed.
While it is easy to see that the referee's probability of
distinguishing the two cases can be amplified by simply repeating the
game many times in sequence, often one would like to stay in the
context of a one-round game. We show that it is indeed possible to
perform such an amplification in parallel. More precisely, for any
eps>0, from the original game we show how one can construct a very
simple one-round game, in which each player now simultaneously
receives poly(1/eps) questions from the original game, and is such
that if the player's original maximum success probability was at most
0.99 in the original game then it becomes at most eps in the repeated
game. Moreover, for a large class of games it will also be the case
that if the value was 1 then it stays 1 in the repeated game. This is
the first time that it is shown how amplification can be performed in
parallel for a large class of games (for more restricted games, such
as unique games, it was already known that independent parallel
repetition is sufficient).
The parallel amplification method we use originates in work of Feige
and Kilian (STOC'94), who proved such an amplification for general
classical (non-entangled) two-player games. Their work predates the
famous parallel repetition theorem due to Raz, which shows that for
classical games it is in fact always possible to perform amplification
by repeating the game many times independently in parallel.