  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$. The 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.
