Nonlocal games with noisy maximally entangled states are decidable

Abstract

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 }^{\ast }(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 }^{\ast }(G,\psi )$. Hence, it is feasible to approximately compute ${\omega }^{\ast }(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}}^{\ast }=\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.

Supercedes arXiv:1904.08832, accepted by SIAM Journal of Computing

References in corpus (3)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Connes' embedding problem and Tsirelson's problem
• Hypercontractivity of quasi-free quantum semigroups