We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige--Kilian transformation [ SIAM J. Comput., 30 (2000), pp. 324--346], and has the property that if the quantum value of the original game $G$ is $v$, then the quantum value of the anchored game $G_{{\perp}}$ is $1 - (1 - \alpha)^2 \cdot (1 - v)$, where $\alpha$ is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game $G$ has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.

In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games.

n this work, we consider the following family of two prover one-round games. In the CHSH_q game, two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q without communicating with the other. The players' objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. This game was introduced by Buhrman and Massar (PRA 2005) as a large alphabet generalization of the celebrated CHSH game---which is one of the most well-studied two-prover games in quantum information theory, and which has a large number of applications to quantum cryptography and quantum complexity.

For a function f over the discrete cube, the total L1 influence of f is defined as the sum of the L1 norm of the discrete derivatives of f in all n directions. In this work, we show that in the case of bounded functions this quantity can be upper bounded by a polynomial in the degree of f (independently of dimension n), resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). We also give an application of our theorem to graph theory, and discuss the connection between the study of bounded functions over the cube and the quantum query complexity of partial functions where Aaronson and Ambainis encountered this question.