A doubly exponential upper bound on noisy EPR states for binary games
share
This paper initiates the study of a class of entangled-games, mono-state games, denoted by (G,ψ), where G is a two-player one-round game and ψ is a bipartite state independent of the game G. In the mono-state game (G,ψ), the players are only allowed to share arbitrary copies of ψ. This paper provides a doubly exponential upper bound on the copies of ψ for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game (G,ψ), if ψ is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than 1. In particular, it includes (1-ϵ)|Ψ〉〈Ψ|+ϵI_2/2⊗I_2/2, an EPR state with an arbitrary depolarizing noise ϵ>0. This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This novel approach provides a new angle to study the decidability of the complexity class MIP^*, a longstanding open problem in quantum complexity theory.
READ FULL TEXT