We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game @math of entangled value 1-eps < 1, the value of the @math -fold repetition of G goes to zero as O((1-eps^c)^k), for some universal constant c 1. Previously parallel repetition with an exponential decay in @math was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call "vector quantum strategy" to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our "quantum correlated sampling lemma" generalizes results of van Dam and Hayden on universal embezzlement.
After the completion of this work two new results established an exponential parallel repetition theorem for two-player one-round games with entangled players in which the distribution on questions is a product distribution. @cite_16 it is shown that the entangled value of games in which the distribution on questions is uniform decreases as @math Very recently @cite_15 extended the result to arbitrary product distributions on the questions, while also removing the dependence on the number of questions: they obtained the bound @math Both results are based on the use of information-theoretic techniques. They are incomparable to ours, as they apply to games in which the acceptance predicate is general but the input distribution is required to be product. In addition, both bounds above have a dependence on the number of answers in the game; while for the case of the classical value such a dependence is necessary @cite_33 , for the entangled value it is not yet known whether it can be avoided.
@cite_15 @cite_16 @cite_33
2952499036 2136241552 1937872493
We show a parallel repetition theorem for the entangled value @math of any two-player one-round game @math where the questions @math to Alice and Bob are drawn from a product distribution on @math . We show that for the @math -fold product @math of the game @math (which represents the game @math played in parallel @math times independently), @math , where @math and @math represent the sets from which the answers of Alice and Bob are drawn. 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. We show that no fixed number of parallel repetitions suffices in order to reduce the error in two-prover one-round proof systems from one constant to another. Our results imply that the recent bounds proven by Ran Raz (1995), showing that the number of rounds that suffice is inversely proportional to the answer length, are nearly best possible.