Nonlocal games with noisy maximally entangled states are decidable
arXiv:2108.09140
Abstract
This paper considers a special class of nonlocal games , where is a two-player one-round game, and is a bipartite state independent of . In the game , the players are allowed to share arbitrarily many copies of . The value of the game , denoted by , is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states . For a noisy maximally entangled state , a two-player one-round game and an arbitrarily small precision , this paper proves an upper bound on the number of copies of for the players to win the game with a probability close to . Hence, it is feasible to approximately compute 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 . 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.
arXiv commentSupercedes arXiv:1904.08832, accepted by SIAM Journal of Computing
References in corpus (11)
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Connes' embedding problem and Tsirelson's problem
- A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
- Hypercontractivity of quasi-free quantum semigroups
- Impossibility of Local State Transformation via Hypercontractivity
- An Invariance Principle for Polytopes
- A New Quantum Data Processing Inequality
- Quantum reverse hypercontractivity
- Compressibility of positive semidefinite factorizations and quantum models
- Limitations on quantum dimensionality reduction
- Quantum soundness of the classical low individual degree test