2021/08/20 by Minglong Qin, Qin, Minglong, Penghui Yao +1 · 2 citations
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2108.09140
openalex publication_date 2021/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper considers a special class of nonlocal games (G,ψ), where G is a two-player one-round game, and ψ is a bipartite state independent of G. In the game (G,ψ), the players are allowed to share arbitrarily many copies of ψ. The value of the game (G,ψ), denoted by ω^*(G,ψ), 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 G and an arbitrarily small precision ε>0, this paper proves an upper bound on the number of copies of ψ for the players to win the game with a probability ε close to ω^*(G,ψ). Hence, it is feasible to approximately compute ω^*(G,ψ) 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 MIP^*=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.