This paper considers a special class of nonlocal games $(G,psi)$, where $G$ is a two-player one-round game, and $psi$ is a bipartite state independent of $G$. In the game $(G,psi)$, the players are allowed to share arbitrarily many copies of $psi$. T
he value of the game $(G,psi)$, denoted by $omega^*(G,psi)$, is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states $psi$. For a noisy maximally entangled state $psi$, a two-player one-round game $G$ and an arbitrarily small precision $epsilon>0$, this paper proves an upper bound on the number of copies of $psi$ for the players to win the game with a probability $epsilon$ close to $omega^*(G,psi)$. Hence, it is feasible to approximately compute $omega^*(G,psi)$ to an arbitrarily precision. Recently, a breakthrough result by Ji, Natarajan, Vidick, Wright and Yuen showed that it is undecidable to approximate the values of nonlocal games to a constant precision when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that $mathrm{MIP}^*=mathrm{RE}$. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications.
In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by $mathrm{D}_{oplus}(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,ldots, x_k)
= f(x_1opluscdotsoplus x_k)$, denoted by $mathrm{CC}^{(k)}(F)$. It is known that $mathrm{CC}^{(k)}(F)leq kcdotmathrm{D}_{oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that [mathrm{D}_{oplus}(f)leq Obig(mathrm{CC}^{(4)}(F)^5big).] Our main tool is a recent result from additive combinatorics due to Sanders. As $mathrm{CC}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $kgeq 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.
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 mathcal{X}timesmathcal{Y}$ to Alice and Bob are drawn from a product distribution on $mathcal{X}timesmathcal
{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) =left(1-(1-omega^*(G))^3right)^{Omegaleft(frac{k}{log(|mathcal{A}| cdot |mathcal{B}|)}right)} $, where $mathcal{A}$ and $mathcal{B}$ represent the sets from which the answers of Alice and Bob are drawn.
