Nonlocal games with noisy maximally entangled states are decidable
Minglong Qin<EMAIL_ADDRESS>)
<EMAIL_ADDRESS>
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 $\br{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)$. A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than $1$. In particular, it includes $(1-\epsilon)\ketbra{\Psi_m}+\epsilon\frac{\id_m}{m}\otimes\frac{\id_m}{m}$ for $\epsilon>0$, where $\ket{\Psi_m}=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}\ket{m,m}$ is an $m$-dimensional maximally entangled state. Hence, it is feasible to approximately compute  $\omega^*\br{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.

§ INTRODUCTION

Interactive proof systems are a fundamental concept to the theory of computing. It was first proposed by Babai [5] and Goldwasser, Micali and Rackoff [33], and later extended to the multiprover setting in [12]. The study of interactive proof systems is at the heart of the theory of computing, including the elegant characterizations $\mathrm{IP}=\mathrm{PSPACE}$ [74, 75] for single-prover interactive proof systems and  $\mathrm{MIP}=\mathrm{NEXP}$ [6] for multiprover interactive proof systems. The latter result further led to the celebrated PCP theorem [2, 3].

The study on the power of interactive proof systems in the context of quantum computing also has a rich history. The model of single-prover quantum interactive proof systems was first studied by Watrous [82], followed by a series of works [57, 59, 34, 44], which finally led to the seminal result $\mathrm{QIP}=\mathrm{PSPACE}$ [43]. Quantum multiprover interactive proof systems are more complicated. A key assumption on the classical multiprover interactive proof systems is that the provers are not allowed to communicate, which means that their only resource in common is the shared randomness. In quantum multiprover interactive proof systems, this assumption is relaxed and the provers are allowed to share entanglement, and the corresponding complexity class is $\mathrm{MIP}^*$ [19]. Surprisingly, understanding the power of $\mathrm{MIP}^*$ turns out to be extremely difficult. A trivial lower bound on $\mathrm{MIP}^*$ is $\mathrm{IP}$, or equivalently $\mathrm{PSPACE}$, which can be easily seen by ignoring all but one provers. Extending the techniques in [6] to the quantum setting, Ito and Vidick proved the containment of $\mathrm{NEXP}$ in $\mathrm{MIP}^*$ [42]. This lower bound was improved by a series of works in various settings [45, 76, 46, 63, 77, 27], which lead to a very recent breakthrough result [47, 48], in which Ji, Natarajan, Vidick, Wright and Yuen constructed a quantum multiprover interactive proof system for the Halting problem, and thus proved that $\mathrm{MIP}^*=\mathrm{RE}$, where $\mathrm{RE}$  is the set of recursively enumerable languages.

This paper concerns two-player one-round games, a core model in computational complexity, which is closely related to multiprover interactive proof systems. A two-player one-round game $G$ is run by three parties, a referee and two non-communicating players. We define $G=\br{\X,\Y,\A,\B,\mu,V}$, where $\X,\Y,\A,\B$ are finite sets, $\mu$ is a distribution over $\X\times\Y$ and $V:\X\times\Y\times\A\times\B\rightarrow\set{0,1}$ is a predicate. Note that all $\X,\Y,\mu,V$ are public. The referee samples a pair of questions $\br{x,y}$ according to $\mu$, and sends $x$ and $y$ to the two players separately. The two players have to provide an answer to the referee by choosing from $\A$ and $\B$, respectively, denoted by $\br{a,b}$. The referee accepts the answers he receives if and only if $V\br{x,y,a,b}=1$. The only restriction on the players' strategies is that they are not allowed to exchange any information once the game has started. In the classical setting, the value of the game $\omega\br{G}$, the highest probability that the referee accepts the game, is

\[\omega\br{G}=\max_{h_A:\X\rightarrow\A\atop h_B:\Y\rightarrow\B}\sum_{xy}\mu\br{x,y}V(x,y,h_A(x),h_B(y)).\]

By the PCP theorem [2, 3] it is $\mathrm{NP}$-hard to approximate $\omega(G)$ within a multiplicative constant. The entangled games, which are the same as the classical games except that the players are allowed to share arbitrary entangled states before they receive the questions, were first introduced by Cleve, Høyer, Toner and Watrous [19]. They also defined the entangled value of a game, denoted by $\omega^*(G)$, to be the supremum of the probability that the referee accepts in a game when the players share entanglement,

\begin{equation}\label{eqn:omegastarG}
\omega^*\br{G}=\lim_{n\rightarrow\infty}\max_{\psi_{AB}\in\D_n\atop \set{P^x_a}_{x,a},\set{Q^y_b}_{y,b}}\sum_{xy}\mu\br{x,y}\sum_{ab}V(x,y,a,b)\Tr\br{\br{P^x_a\otimes Q^y_b}\psi_{AB}},
\end{equation}

where $\D_n$ is the set of $n$-dimensional density operators, $\set{P^x_a}_a$ and $\set{Q^y_b}_b$ are POVMs for any $x
\in\X,y\in\Y$, respectively. Namely, $\sum_{a\in\A}P^x_a=\id$, $\sum_{b\in\B}Q^y_b=\id$, $P^x_a\geq 0$ and  $Q^y_b\geq 0$.

The quantities $\omega^*\br{G}$ of nonlocal games are important in both physics and computer science. Cleve et al. [19] discovered the fact that $\omega^*(G)>\omega(G)$ for the so-called CHSH games [18] gives a re-interpretation of the Bell's inequalities [10], which plays a central role in all aspects of quantum mechanics. It is nowadays known that there exist games for which $\omega^*(G)=1$ while $\omega(G)$ is arbitrarily small [70, 1]. A large body of works have also been devoted to understanding the hardness of computing $\omega^*\br{G}$. It was shown in [53, 41] that approximating $\omega^*(G)$ to an inverse-polynomial accuracy is $\mathrm{NP}$-hard. Ji proved that it is $\mathrm{QMA}$-hard to approximate $\omega^*(G)$ for multiplayer games to an inverse-exponential accuracy [45]. Later it was shown by the same author that approximating $\omega^*(G)$ for multiplayer games to an inverse-polynomial accuracy is $\mathrm{MIP}^*$-complete [46]. Slofstra in his seminal results [76, 77] proved that determining whether $\omega^*(G)=1$ for general games $G$ is undecidable. Moreover, a positive answer to the so-called Tsirelson's problem (see e.g. [28]) implies the existence of an algorithm approximating $\omega^*(G)$ for general games. It is known that  Tsirelson's problem is related to Connes' Embedding Conjecture [21], which was a longstanding open problem in functional analysis [50, 67]. In [47, 48], Ji et al. completely resolved this problem by proving that even approximating $\omega^*(G)$ for two-player nonlocal games to a constant accuracy is undecidable.

On the other hand, for a few known classes of games, $\omega^*(G)$ is computable, and sometimes computing $\omega^*(G)$ is even easier than computing $\omega(G)$. Cleve et al. in [19] gave a polynomial-time algorithm to exactly compute $\omega^*(G)$ for XOR games $G$ building on the work of Tsirelson [17]. Kempe, Regev and Toner later presented a polynomial-time algorithm for $\omega^*(G)$ for unique games with a factor $6$ approximation to $1-\omega^*(G)$ [52]. However, it is $\mathrm{NP}$-hard to approximate $\omega(G)$ for XOR games within a factor of $11/12+\epsilon$ and also $\mathrm{NP}$-hard to approximate $\omega(G)$ for $k$-XOR games within a factor of $1/2+\epsilon$ for $k \geq 3$ [38]. Classical unique games are conjectured to be NP-hard [54] as well.
Both of the algorithms in [19, 52] are based on convex optimization. In particular, a hierarchy of semidefinite programs was proposed in [64]. The optimal values converge to $\omega^*_{\mathrm{co}}(G)$, which are the values of games when the players employ commutative strategies, and thus $\omega_{\mathrm{co}}\br{G}$ is an upper bound on $\omega^*(G)$. However, the speed of convergence is unknown. There are some other classes of nonlocal games whose entangled values are known to be computable [85]. Readers may refer to the survey [81] for more details.

§.§ Main results

In this paper, we prove that for any nonlocal game, if the players share arbitrarily many copies of noisy maximally entangled states (MES) of a fixed dimension, then it is feasible to approximate the supremum of the winning probability to an arbitrary precision.

Given a nonlocal game $G$, for any integer $m\geq2$, if the players share arbitrarily many copies of $m$-dimensional noisy MES $\Psi_{\epsilon}=\br{1-\epsilon}\ketbra{\Psi_m}+\epsilon\frac{\id_m}{m}\otimes\frac{\id_m}{m}$ for any $\epsilon>0$, where $\ket{\Psi_m}=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}\ket{i,i}$ is an $m$-dimensional MES, there exists an explicitly computable $D=D(\epsilon,\delta,m,G)$ such that it suffices for the players to share $D$ copies of $\psi$ to achieve the winning probability at least $\omega^*\br{G,\Psi_{\epsilon}}-\delta$, where $\omega^*\br{G,\Psi_{\epsilon}}$ represents the value of the game, which is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states $\Psi_{\epsilon}$. Thus, it is feasible to approximate the value of the game $\omega^*(G,\Psi_{\epsilon})$ to arbitrary precision.

A natural and naive approach is to prove that the players are able to produce arbitrarily many copies of noisy MESs with bounded copies of perfect MESs and preshared classical randomness. The main result would be trivial if this were possible. However, this is not the case since the entanglement between the two players does not increase via local operations.

Ji et al. in [47] showed that if the players share arbitrarily many copies of perfect MES, then approximating the values of the games is as difficult as the Halting problem. Thus our result implies that the hardness of approximating nonlocal games is not robust against the noise of the preshared states.

The techniques developed in this paper are completely different from all previous approaches [19, 52, 64, 8, 28, 76, 85, 77, 47] . We generalize the framework of Boolean analysis, a well-studied and fruitful topic in theoretical computer science [66], to matrix spaces and reduce the problem to local state transformations [25], a quantum analog of non-interactive simulations of joint distributions. This approach provides a new perspective with novel tools to study entangled nonlocal games. We develop a series of results about Fourier analysis on matrix spaces, which might be of independent of interest and have applications in quantum property testing, quantum machine learning, etc.

Non-interactive simulations of joint distributions are a fundamental problem in information theory and communication complexity. Consider two non-communicating players Alice and Bob, and suppose they are provided a sequence of independent samples $\br{x_1,y_1},\br{x_2,y_2},\ldots$ from a joint distribution $\mu$ on $\X\times\Y$, where Alice observes $x_1,x_2,\ldots$ and Bob observes $y_1,y_2,\ldots$. Without communicating with each other, for what joint distribution $\nu$ can Alice and Bob sample? The research on this problem dates back to the classic works by Gács and Körner [29], Wyner [88] and Witsenhausen [86], followed by fruitful subsequent works (see, for example, [51] and the references therein). Recently, Ghazi, Kamath and Sudan in [32] studied the decidability of non-interactive simulations of joint distributions by introducing a framework built on the theory of Boolean analysis and Hermitian analysis [62, 61, 66]. Using this framework, the decidability is resolved in subsequent works [24, 31].

In the quantum universe, it is natural to consider the quantum analog of non-interactive simulations of joint distributions, which is also referred to as local state transformations. Suppose the two non-communicating players Alice and Bob are provided with arbitrarily many copies of bipartite quantum states $\psi_{AB}$. Without communicating with each other, what bipartite quantum state $\phi_{AB}$ can Alice and Bob jointly create? Delgosha and Beigi first studied this problem and gave a necessary condition for the exact local state transformation of $\psi_{AB}$ to $\phi_{AB}$ [25]. Other than this result, not much about this problem is known. Our paper essentially resolves the decidability of local state transformations, when $\psi_{AB}$ is a noisy MES and the target state $\phi_{AB}$ is a classical bipartite distribution. The proofs adopt the framework laid down in [32] and its subsequent works [24, 31]. It heavily uses Boolean analysis and Hermitian analysis on Gaussian spaces, which have been intensively studied and have rich applications in theoretical computer science [66]. Some key components in Boolean analysis and Hermitian analysis, such as hypercontractive inequalities, have also been extended to quantum settings in various aspects, which have led to several interesting applications [11, 60, 79, 56, 25, 22].
However, much less is known about Fourier analysis on matrix spaces or quantum operations compared to Boolean analysis or Hermitian analysis on Gaussian spaces. We systematically develop Fourier analysis on random matrix spaces, which are hybrids of matrix spaces and Gaussian spaces. In particular, this paper proves a quantum invariance principle and a hypercontractive inequality for random operators, successfully generalizing the framework established in [32, 24, 31] to the quantum setting. Invariance principles are a core result in the analysis of Boolean functions, which have a number of applications in various areas(see [37] and the references therein). To the best of our knowledge, this is the first quantum invariance principle and the result in this paper is the first application of the invariance principle in quantum complexity theory. We believe that the tools developed in this paper are interesting in their own right and have further applications.

§.§ Technical Contributions
In this paper, we treat the set $\M_m$  of $m\times m$ matrices as a Hilbert space of dimension $m^2$ by introducing the inner product $\innerproduct{A}{B}=\frac{1}{m}\Tr A^{\dagger}B$. Let $\B=\set{\B_0,\B_1,\ldots,\B_{m^2-1}}$ be an orthonormal basis in $\M_m$ with all elements being Hermitian and $\B_0=\id$, whose existence is guaranteed by <ref>. It is easy to verify that the set $\set{\B_{\sigma}:\sigma\in\set{0,\ldots, m^2-1}^n}$, where $\B_{\sigma}\defeq\B_{\sigma_1}\otimes\B_{\sigma_2}\otimes\ldots\otimes\B_{\sigma_n}$, forms an orthonormal basis in $\M_m^{\otimes n}$. Any operator $P\in\M_m^{\otimes n}$ can be expressed as

\begin{equation}\label{eqn:Pexpression}
P=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\B_{\sigma},
\end{equation}

which can be viewed as a Fourier expansion of $P$ in terms of the basis $\B$, where $[n]_{\geq 0}$ represents the set $\set{0,\ldots, n-1}$.

§.§ Quantum invariance principle and quantum hypercontractive inequality

Invariance principles are a powerful tool in Boolean analysis, which has found applications in various areas in theoretical computer science, such as inapproximation theory, derandomization, voting theory, etc [62]. Let's recall the invariance principle for functions in [62]. Let $f:\set{1,-1}^n\rightarrow\reals$ be a bounded-degree multilinear polynomial with small influence for all variables. An invariance principle asserts that

\begin{equation}\label{eqn:inv}
\expec{\mathbf{x}\sim\set{1,-1}^n}{\Psi\br{f\br{\mathbf{x}}}}\approx\expec{\mathbf{g}\sim\gamma_n}{\Psi\br{f\br{\mathbf{g}}}}
\end{equation}

for any Lipschitz continuous function $\Psi:\reals\rightarrow\reals$, where $\gamma_n$ is a standard $n$-dimensional normal distribution. Here the expression "$f\br{\mathbf{g}}$" is an abuse of notation indicating that the real numbers $\mathbf{g}_1,\ldots,\mathbf{g}_n$ are substituted into $f$'s Fourier expansion. The power of Eq. <ref> is that we are able to interchange arbitrary random variables with Gaussian random variables.

One of our main contributions is establishing a quantum invariance principle. Let $P\in\M_m^{\otimes n}$ be a Hermitian operator with a Fourier expansion in Eq. <ref> satisfying that all registers have low influence (which will be specified). Here we view $P$ as an operator acting on $n$-partite quantum systems, where each system is of dimension $m$. The term "register" is referred to each system. For a $\C^2$ piecewise polynomial $\Psi$, it holds that

\begin{equation}\label{eqn:qinv}
\frac{1}{m^n}\Tr~\Psi\br{\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\B_{\sigma}}\approx\expec{\mathbf{g}\sim\gamma_{\br{m^2-1}n}}{\Psi\br{\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\prod_{i=1}^{n}\mathbf{g}_{i,\sigma_i}}},
\end{equation}

where $\mathbf{g}=\br{\mathbf{g}_{1,1},\ldots,\mathbf{g}_{_1,m^2-1},\ldots, \mathbf{g}_{n,1},\ldots,\mathbf{g}_{_1,m^2-1}}\sim\gamma_{n\br{m^2-1}}$ and $\mathbf{g}_{1,0}=\cdots=\mathbf{g}_{n,0}=1$.
Eq. <ref> enables us to turn the quantum registers to Gaussian random variables, which gives polynomials in Gaussian spaces.

The proof of Eq. <ref> employs the well-known Lindeberg-style method (see e.g., Chapter 11 in [66]). It first substitutes $\Psi$ by a $\C^{\infty}$ approximation $\Psi'$, whose existence follows by standard results in approximation theory. Then by expanding both sides of Eq. <ref> to the third-order derivatives via Taylor series, we can prove that the difference between the left-hand side and the right-hand side is upper bounded by the norms of the third-order terms in the Taylor expansion of $\Psi'$. Applying the hypercontractive inequality for Boolean variables and the one for Gaussian variables, respectively, we can see that the difference between the two sides is small for functions with all variables having low influence.

Generalizing the Lindeberg-style method to matrices is not an easy task due to the non-commutativity of matrices. To this end, we need to investigate the analytical properties of matrix-functions. We use Fréchet derivatives, a notion of derivatives in Banach spaces, in which a similar form of Taylor expansions exists.  The differentiability of real functions and of matrix-functions with respect to Fréchet derivatives share many properties in common [73]. We follow the same mechanism as the original Lindeberg-style method by substituting the basis elements with Gaussian variables and obtain random operators, which are hybrids of operators and random variables. The Taylor expansions of matrix-valued functions are in general complicated due to the nature of the non-commutativity as well. Fortunately, it suffices to prove a quantum invariance principle for a $\C^2$ piecewise polynomial for our purpose.

We prove that the difference between the two sides in Eq. <ref> is upper bounded by the 3rd order term in the Taylor expansion of $\Psi$, which, in turn, is upper bounded by the product of its $2$-norm and the square of its $4$-norm. Applying the hypercontractive inequality for random operators, we are able to upper bound the difference by the cube of its $2$-norm, which is further upper bounded by the influences of all registers.

Another difficulty that follows is to prove a hypercontractive inequality for random operators, which is expected to show that the $4$-norm of a bounded-degree random operator can be upper bounded by its $2$-norm. As random operators are hybrids of operators and Gaussian variables, our proof delicately combines the hypercontractivity for Gaussian variables and the hypercontractivity for operators. The former has already been proved in [87]. King in [55] proved a hypercontractive inequality for unital qubit channels, which immediately implies a hypercontractive inequality for operators in $\M_2^{\otimes n}$. However, since his proof heavily relies on the properties of qubit channels, it fails to generalize to $\M_m^{\otimes n}$ for $m>2$. This paper focuses only on the hypercontractivity for depolarizing channels in any dimension. Thus we use the properties specific to depolarizing channels to prove a hypercontractive inequality for operators via an inductive argument. The desired result follows after we combine a hypercontractive inequality for operators and a hypercontractive inequality for random variables in [87].

§.§ Quantum dimension reductions
Dimension reductions are a versatile tool in theoretical computer science. One of the most well-known dimension reduction techniques is arguably the Johnson–Lindenstrauss lemma [49], which enables us to embed a set of points from a high-dimensional space into a space of much lower dimension with slight distortion. Dimension reductions are a natural approach to upper bound the complexity of quantum nonlocal games. However, proving quantum dimension reductions seems to be difficult and sometimes even impossible [36, 78]. In this paper, we present a new quantum dimension reduction technique by establishing a new quantum invariance principle and combining it with a recent dimension reduction result in Gaussian spaces [31].

To the best of our knowledge, this is the first invariance principle in the quantum setting. We are also not aware of any other invariance principle proved via Fréchet derivatives prior to our result. We believe our invariance principle and quantum dimension reduction are interesting in their own right and should have further applications.

§.§ Proof Overview

We are interested in the decidability of the following decision problem, which is a special case of local state transformations.

Q. Given $0<\epsilon,\delta<1$, integers $t,m\geq 2$ and a distribution $\mu$ over $[t]\times[t]$, suppose Alice and Bob share arbitrarily many copies of the bipartite quantum states $\Psi_{\epsilon}=\br{1-\epsilon}\ketbra{\Psi}+\epsilon\frac{\id_m}{m}\otimes\frac{\id_m}{m}$, where $\ket{\Psi}=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}\ket{i,i}$ is an $m$-dimensional maximally entangled state.

Yes. Alice and Bob are able to jointly sample a distribution $\mu'$ over $[t]\times[t]$ which is $\delta$-close to $\mu$, i.e., $\onenorm{\mu'-\mu}\leq\delta$.

No. Any distribution $\mu'$ over $[t]\times[t]$ that Alice and Bob can jointly sample is $2\delta$-far from $\mu$, i.e., $\onenorm{\mu-\mu'}\geq2\delta$.

§.§ Special case: $\mu$ is a binary distribution

We first consider the special case that $\mu$ is a binary distribution, namely $t=2$. Suppose the POVM's performed by Alice and Bob are  $\set{P,\id-P}$ and $\set{Q,\id-Q}$, respectively, where $P, Q\in\H_m^{\otimes n}$ and $0\leq P,Q\leq\id$. Here $\H_m^{\otimes n}$ represents the set of all Hermitian operators acting on an $n$-qudit quantum system, where each qudit is of dimension $m$. The proof is to construct a universal bound $D$, which is independent of the measurements, and transformations $f_n,g_n:\H_m^{\otimes n}\rightarrow\H_m^{\otimes D}$, such that the requirements in <ref> are satisfied.

* $0\leq f_n\br{P}\leq\id~\mbox{and}~0\leq g_n\br{Q}\leq\id;$

* $\frac{1}{m^n}\Tr~P\approx\frac{1}{m^D}\Tr~f_n\br{P} ~\mbox{and}~ \frac{1}{m^n}\Tr~Q_n\approx\frac{1}{m^D}\Tr~g_n\br{Q};$

* $\Tr\br{\br{P\otimes Q}\Psi_{\epsilon}^{\otimes n}}\approx\Tr\br{\br{f_n\br{P}\otimes g_n\br{Q}}\Psi_{\epsilon}^{\otimes D}}.$

Requirements for binary output distributions

The first item implies that $\set{f_n\br{P},\id-f_n\br{P}}$ and $\set{g_n\br{Q},\id-g_n\br{Q}}$ are both valid POVMs. The second item implies that the probability that Alice outputs $0$ is almost unchanged under the transformation $f_n$.  Same for the probability that Bob outputs $0$. The last item implies that the probability that both Alice and Bob output $0$ is almost unchanged. As Alice's and Bob's outputs are both binary, it follows that the distribution of the joint output is almost unchanged.

The constructions of the transformations $f_n$ and $g_n$ are built on the framework introduced in [32], which, in turn, was based on the results in Boolean analysis and Hermitian analysis [62, 61]. Let $\A=\set{\A_0,\ldots,\A_{m^2-1}}$ and $\B=\set{\B_0,\ldots,\B_{m^2-1}}$, which will be specified later, be two properly chosen orthonormal bases in $\M_m$. The Fourier expansions of $P$ and $Q$ on bases $\A$ and $\B$ can be expressed as

\[P=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\A_{\sigma}~\mbox{and}~Q=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{Q}\br{\sigma}\B_{\sigma},\]

respectively, where $[n]_{\geq 0}$ represents the set $\set{0,\ldots, n-1}$. The steps for constructing the transformations $f_n$ and $g_n$ are specified as follows.

* Smooth operators.

* bounded-degree approximation.

We first convert the operators $\br{P,Q}$ to a new pair of operators that can be approximated by bounded-degree operators via smoothing operations. The standard techniques in Boolean analysis [66] motivate us to apply a noise operator $\Delta_{\rho}$ for some $\rho\in(0,1)$ to both $P$ and $Q$. Note that the noise operator is also referred to as a depolarizing channel in quantum information theory [65], and its counterpart in the Gaussian space is called Ornstein-Uhlenbeck operator.

Then we obtain

\[\Delta_{\rho}P=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\rho^{|\sigma|}\A_{\sigma}~\mbox{and}~\Delta_{\rho}Q=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{Q}\br{\sigma}\rho^{|\sigma|}\B_{\sigma},\]

where $|\sigma|=\abs{\set{i:\sigma_i\neq 0}}$.
Here $\Delta_{\rho}P$ and $\Delta_{\rho}Q$ are independent of the choices of bases by <ref> and <ref> item 1. It is not hard to verify that the requirements specified in item 1 and item 2 in <ref> are satisfied. To meet the requirements in item 3, we need the notion of quantum maximal correlation introduced by Beigi [9], which extends the maximal correlation coefficients [39, 30, 71] in classical information theory. Note that after smoothing the operators, the weights of high-degree parts of both $P$ and $Q$, namely, the parts with high $\abs{\sigma}$, decrease exponentially. Thus, both operators can be approximated by bounded-degree operators.

* Joint regularity.

* bounded-degree approximation;

* bounded number of high-influential registers.

We prove that the number of high-influential registers is bounded. Let $H$ be the set of all high-influential registers.  The influence of a register to a Hermitian operator on a multipartite quantum system is defined in <ref>, which was first introduced by Montanaro in [60], analogous to the influence defined in Boolean analysis [66]. It informally speaking, measures how much the register can influence the operator. This step follows by quantizing a well-known result in Boolean analysis. For any bounded function, the total influence, i.e., the summation of the influences of all variables, is upper bounded by the degree of the function. Note that both $P$ and $Q$ can be approximated by bounded-degree operators after the first step. By Markov's inequality, the size of $H$ can be bounded.

* Invariance from operators to random operators.

* bounded-degree approximation;

* bounded number of quantum registers;

* unbounded number of Gaussian variables.

In this step, we use correlated Gaussian variables to substitute for all the quantum registers in $P$ and $Q$ with low influence, after which we get random operators.

Prior to the substitution, we prove that there exist bases $\A$ and $\B$ such that

\[\Tr\br{\br{\A_i\otimes\B_j}\psi_{AB}}=\delta_{i,j}c_i,\]

for $1=c_0\geq c_1\geq c_2\geq \cdots\geq c_{m^2-1}\geq 0$, where $\A_0=\B_0=\id$.

\begin{equation}\label{eqn:pqreg}
\Tr\br{\br{P\otimes Q}\psi_{AB}^{\otimes n}}=\sum_{\sigma\in[m^2]_{\geq 0}^n}c_{\sigma}\widehat{P}\br{\sigma}\widehat{Q}\br{\sigma},
\end{equation}

where $c_{\sigma}=c_{\sigma_1}\cdot c_{\sigma_2}\cdots c_{\sigma_n}$ for any $\sigma\in[m^2]_{\geq 0}^n$.

We now introduce independent joint random variables
$$\set{\br{\mathbf{g}_{i,j},\mathbf{h}_{i,j}}}_{i\notin H,j\in[m^2]_{\geq 0}},$$
where $\mathbf{g}_{i,0}=\mathbf{h}_{i,0}=1$ and $\br{\mathbf{g}_{i,j},\mathbf{h}_{i,j}}\sim\G_{c_j}$ for $i\notin H,j\geq 1$ and $\rho$-correlated two-dimensional Gaussian distribution $\G_{\rho}$. Given the Fourier expansions of $P$ and $Q$, we substitute all the matrix bases in the quantum registers not in $H$ by $\br{\mathbf{g}_{i,j},\mathbf{h}_{i,j}}$, respectively, to obtain the random operators distributed over all operators acting on the registers in $H$ as follows.

\begin{equation}\label{eqn:intro2}
\mathbf{P}=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\br{\prod_{i\notin H}\mathbf{g}_{i,\sigma_i}}\A_{\sigma_H}\end{equation}

\mathbf{Q}=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{Q}\br{\sigma}\br{\prod_{i\notin H}\mathbf{h}_{i,\sigma_i}}
\B_{\sigma_H}.$$

It is easy to verify the requirements specified by item 2 and item 3 in <ref> are satisfied in expectation. However, $\mathbf{P}$ and $\mathbf{Q}$ are in general not POVM elements, which means that item 1 is violated. To meet item 1, it suffices to show that both of the random operators are $\ell_2$-close to POVM elements in expectation. Let $\R:\H_m^{\otimes n}\rightarrow\H_m^{\otimes n}$ be a rounding map of the set of POVM elements, namely $\R\br{X}=\arg\min\set{\twonorm{X-Y}:0\leq Y\leq\id}$, where $\twonorm{\cdot}$ is the Schatten 2-norm. Hence, we prove that

\begin{equation}\label{eqn:PRP}
\expec{}{\twonorm{\mathbf{P}-\R\br{\mathbf{P}}}^2}\approx 0~\mbox{and}~\expec{}{\norm{\mathbf{Q}-\R\br{\mathbf{Q}}}^2_2}\approx 0.
\end{equation}

It is not hard to verify that
$\twonorm{\R(X)-X}^2=\Tr~\theta\br{X}$, where

\begin{equation}\label{eqn:zetasingle}
\theta\br{x}=\begin{cases}
(x-1)^2~&\mbox{if $x\geq 1$}\\
x^2~&\mbox{if $x\leq 0$}\\
\end{cases}
\end{equation}

Thus, proving <ref> is equivalent to proving that

\begin{equation}\label{eqn:PthetaP}
\expec{}{\Tr~\theta\br{\mathbf{P}}}\approx0~\mbox{and}~\expec{}{\Tr~\theta\br{\mathbf{Q}}}\approx0.
\end{equation}

As described above, we need to prove an invariance principle for the function $\theta$ defined in Eq. <ref>, which is a $\C^1$ piecewise polynomial. We are able to construct a $\C^2$ approximation of $\theta$, denoted by $\theta_{\lambda}$, which is also a piecewise polynomial. We prove an invariance principle for $\theta_{\lambda}\br{\cdot}$ and show that both $\expec{}{\sum_i\Tr~\theta\br{\mathbf{P}_i}}$ and $\expec{}{\sum_i\Tr~\theta\br{\mathbf{Q}_i}}$ are upper bounded by the 3rd order terms in the Taylor expansion of $\theta_{\lambda}$, which, in turn, are upper bounded by the cube of their $2$-norm due to a hypercontractive inequality for random operators.

* Dimension reduction.

* bounded number of quantum registers;

* bounded number of Gaussian variables.

For any $\sigma_H\in[m^2]^{|H|}_{\geq 0}$, let

\[p_{\sigma_H}\br{\vec{\mathbf{g}}}=\sum_{\tau\in[m^2]^n_{\geq 0}:\tau_H=\sigma_H}\widehat{P}\br{\tau}\br{\prod_{i\notin H}\mathbf{g}_{i,\tau_i}}\]

\[q_{\sigma_H}\br{\vec{\mathbf{h}}}=\sum_{\tau\in[m^2]^n_{\geq 0}:\tau_H=\sigma_H}\widehat{Q}\br{\tau}\br{\prod_{i\notin H}\mathbf{g}_{i,\tau_i}},\]

where $p_{\sigma_H},q_{\sigma_H}:\reals^{\br{m^2-1}(n-|H|)}\rightarrow\reals$ and
\[\vec{\mathbf{g}}=\br{\mathbf{g}_{i,j}}_{i\notin H,j\in[m^2-1]}, \vec{\mathbf{h}}=\br{\mathbf{h}_{i,j}}_{i\notin H,j\in[m^2-1]}.\]

$\br{p_{\sigma_H}\br{\vec{\mathbf{g}}}}_{\sigma_H\in[m^2]^{|H|}_{\geq 0}}$ and $\br{q_{\sigma_H}\br{\vec{\mathbf{h}}}}_{\sigma_H\in[m^2]^{|H|}_{\geq 0}}$ are the Fourier coefficients of $\mathbf{P}$ and $\mathbf{Q}$, respectively. Namely,

\begin{equation}\label{eqn:intro3}
\mathbf{P}=\sum_{\sigma_H\in[m^2]_{\geq 0}^{|H|}}p_{\sigma_H}\br{\vec{\mathbf{g}}}\A_{\sigma_H}~\mbox{and}~\mathbf{Q}=\sum_{\sigma_H\in[m^2]_{\geq 0}^{|H|}}q_{\sigma_H}\br{\vec{\mathbf{h}}}\B_{\sigma_H},
\end{equation}

After applying the dimension reduction in [31] to polynomials $\br{p_{\sigma_H},q_{\sigma_H}}$ , the number of Gaussian random variables is reduced to a bounded number. Meanwhile, all the requirements listed in <ref> are still satisfied in expectation.

* Smooth random operators.

* bounded-degree approximation;

* bounded number of quantum registers;

* bounded number of Gaussian variables.

The remaining steps are mainly concerned with removing the Gaussian variables in $\mathbf{P}$ and $\mathbf{Q}$ to obtain  POVM elements. To this end, we perform transformations similar to the ones in the previous steps.  We first apply the noise operator again to both operators to reduce the weight of the high degree parts.

* Multilinearization.

* bounded-degree approximation;

* bounded number of quantum registers;

* bounded number of Gaussian variables;

* multilinear.

The degrees of Gaussian variables occurring in the functions might be unbounded. Prior to the substitution of Gaussian variables by quantum registers, we need the multilinearization lemma in [31] to reduce the power of each Gaussian variable to either $0$ or $1$. Namely, the polynomials $p_{\sigma_H}$'s and $q_{\sigma_H}$'s in Eq. <ref> are all multilinear after this step.

* Invariance from random operators to operators.

* bounded number of quantum registers.

In the final step, we substitute the Gaussian variables by properly chosen basis elements and round both operators to  POVM elements. Again, we need to apply a quantum invariance principle to ensure that all the requirements in <ref> are satisfied.

§.§ General case: $\mu$ is a general bipartite distribution

Suppose Alice and Bob share $n$ copies of $\Psi_{\epsilon}$ and the POVMs Alice and Bob peform are $\br{P_1,\ldots, P_t}$ and $\br{Q_1,\ldots, Q_t}$, respectively.
We need to construct a universal bound $D$, which is independent of the measurements, and the transformations $f_n,g_n:\H_m^{\otimes n}\rightarrow\H_m^{\otimes D}$ such that the requirements in <ref> are satisfied. Note that item 1 (b) requires that the output of the  transformations is a pair of sub-POVMs rather than POVMs. However, it can be proved that this technical constraint does not affect our final conclusion.

Let $\br{\widetilde{P}_1,\ldots, \widetilde{P}_t}=f_n\br{P_1,\ldots, P_t}$ and $\br{\widetilde{Q}_1,\ldots,\widetilde{Q}_t}=g_n\br{Q_1,\ldots, Q_t}$.

* $\br{\widetilde{P}_1,\ldots,\widetilde{P}_t}$ and $\br{\widetilde{Q}_1,\ldots,\widetilde{Q}_t}$ are valid sub-POVMs. Namely,

* $\forall i,j\in[t]~ 0\leq\widetilde{P}_i\leq \id$ and $0\leq\widetilde{Q}_i\leq \id$.

* $\sum_{i=1}^{t}\widetilde{P}_i\leq\id$ and $\sum_{i=1}^{t}\widetilde{Q}_i\leq\id$.

* $\forall i,j\in[t]~ \Tr\br{\br{P_i\otimes Q_j}\Psi_m^{\otimes n}}\approx\Tr\br{\br{\widetilde{P}_i\otimes\widetilde{Q}_j}\Psi_m^{\otimes D}}.$

Requirements for general output distributions

A natural approach is to apply the transformations $f_n$ and $g_n$ constructed for the binary case to all $P_i$'s and $Q_i$'s, respectively. Note that Eq.<ref> and the quantum invariance principle guarantee item 1(a). However, as the transformations are applied to $P_i$'s and $Q_i$'s individually, we cannot directly conclude item 1(b). The difficulty arises when trying to prove item 1(b) in <ref> as it enforces global constraints on $P_i$'s and $Q_i$'s.

Given $X_1,\dots,X_t\in\H_m^{\otimes n}$, let
\[\R\br{X_1,\ldots,X_t}=\arg\min\set{\sum_{i=1}^t\twonorm{X_i-Y_i}^2:\br{\forall i}0\leq Y_i\leq\id, \sum_i Y_i\leq\id}\]

be a rounding map of the set of all sub-POVMs. And

\begin{equation}\label{eqn:theta}
\theta\br{X_1,\ldots, X_t}=\twonorm{\br{X_1,\ldots,X_t}-\R\br{X_1,\ldots, X_t}}^2.
\end{equation}

To obtain a similar result as  Eq. <ref>, an intuitive approach is to prove a quantum version of the multivariable invariance principle [40]. However, this is technically challenging. In the classical setting, i.e., all $X_i$'s are real numbers, to establish a multivariable invariance principle, it requires us to compute the Taylor expansion of a smooth approximating function for $\theta$ [40]. However, the high-order Fréchet derivatives of the functions with multiple matrices as inputs are highly involved in general.

To avoid the difficulty of analyzing functions with multiple matrices as inputs, we upper bound the function $\theta$ in Eq. <ref> by a function that takes only a single matrix as input. Namely,

\begin{equation}\label{eqn:rzeta}
\theta\br{P_1,\ldots, P_t}\leq O\br{t\cdot\sum_{i=1}^t\Tr~\zeta\br{P_i}},
\end{equation}

\begin{equation}\label{eqn:introzeta}
\zeta\br{x}=\begin{cases}x^2~&\mbox{if $x\leq 0$}\\ 0~&\mbox{otherwise}\end{cases}.
\end{equation}

With Eq. <ref>, it is sufficient for us to prove that

\begin{equation}\label{eqn:PzetaP}
\expec{}{\sum_i\Tr~\zeta\br{\mathbf{P}_i}}\approx0~\mbox{and}~\expec{}{\sum_i\Tr~\zeta\br{\mathbf{Q}_i}}\approx0,
\end{equation}

which is again obtained by a quantum invariance principle described in the previous subsection.

The constructions of the maps $f_n$ and $g_n$ are summarized in <ref>.

$P$   $Q$   $\H_m^{\otimes n}$
$ 0\leq P,Q\leq\id$

objective: bounded deg<ref>$P^{(1)}$$Q^{(1)}$$\H_m^{\otimes n}$
$ 0\leq P^{(1)},Q^{(1)}\leq\id$

bounded deg
bounded high inf registers<ref>$P^{(1)}$$Q^{(1)}$$\H_m^{\otimes n}$
$ 0\leq P^{(1)},Q^{(1)}\leq\id$

Invariance principle
bounded deg
bounded matrix bases
unbounded Gaussian vars<ref>$\mathbf{P}^{(2)}$$\mathbf{Q}^{(2)}$$L^2\br{\H^{\otimes h}_m,\gamma_{2(m^2-1)(n-h)}}$

Dimension reduction
bounded q. registers
bounded Gausian vars<ref>$\mathbf{P}^{(3)}$$\mathbf{Q}^{(3)}$$L^2\br{\H^{\otimes h}_m,\gamma_{n_0}}$

bounded q. registers
bounded Gaussian vars
bounded deg<ref>$\mathbf{P}^{(4)}$$\mathbf{Q}^{(4)}$$L^2\br{\H^{\otimes h}_m,\gamma_{n_0}}$

bounded q. registers
bounded Gaussian vars
bounded deg & multilinear<ref>$\mathbf{P}^{(5)}$$\mathbf{Q}^{(5)}$$L^2\br{\H^{\otimes h}_m,\gamma_{n_0n_1}}$

Invariance principle
bounded q. registers<ref>$P^{(6)}$$Q^{(6)}$$\H_m^{h+n_0n_1}$

Construction of the transformations

Note that in nonlocal games the players perform different measurements for different inputs. Thus, we may encounter consistency issues when applying the transformations mentioned above to nonlocal games. Suppose the players' strategies are $\br{\set{P,\id-P},\set{Q,\id-Q}}$ and $\br{\set{P,\id-P},\set{Q',\id-Q'}}$ for questions $(x,y)$ and $\br{x,y'}$, respectively. We need to ensure that the resulting POVMs on Alice's side are same in both cases. Namely, the transformation for each player should be independent of the other player. Note that only the regularization and dimension reduction steps jointly depend on both operators. Fortunately, the dependence between the two players in both steps can be removed by applying a union bound on all of the possible question pairs.

§ ORGANIZATION
<Ref> summarizes some useful concepts and basic facts on quantum mechanics, the analysis on Gaussian spaces, matrix spaces and random operators. <Ref> introduces the notion of quantum maximal correlations, a key concept in this work, with several crucial properties. The main results and the proofs are stated and proved in <Ref>. A summary with further work and open problems are listed in <Ref>. The step of smoothing operators is in  <Ref>.  <Ref> proves a joint regularity lemma. <Ref> proves a hypercontractive inequality for random operators. <Ref> presents a reduction from the rounding distance to the function $\Tr\zeta\br{\cdot}$. Quantum invariance principles are proved in <Ref>. <Ref> proves a dimension reduction for random operators. The step of smoothing random operators is presented in <Ref>. The step of multilinearization is proved in <Ref>. <Ref> summarizes  basic facts on Fréchet derivatives. <Ref> and <Ref> present some deferred proofs. <Ref> summarizes all the notations in a table for readers to look up.

§ PRELIMINARIES

This paper uses a number of notations. For readers' convenience, all the notations are summarized in <ref>. For an integer $n\geq 1$, let $[n]$ and $[n]_{\geq 0}$ represent the sets $\set{1,\ldots, n}$ and $\set{0,\ldots, n-1}$, respectively. Given a finite set $\X$ and a natural number  $k$, let $\X^k$ be the set $\X\times\cdots\times\X$, the Cartesian product of $\X$, $k$ times. Given $a=a_1,\ldots, a_k$ and a set $S\subseteq[k]$, we write $a_S$ to represent the projection of $a$ to the coordinates specified in $S$. For any $i\in[k]$, $a_{-i}$ represents $a_1,\ldots, a_{i-1},a_{i+1},\ldots, a_n$ and $a_{<i}$ represents $a_1,\ldots, a_{i-1}$. $a_{\leq i},a_{>i}, a_{\geq i}$ are defined similarly. For any $\sigma\in\mathbb{Z}_{\geq 0}^k$, we define $\abs{\sigma}=\abs{\set{i:\sigma_i\neq 0}}$ and $\mathrm{wt}\br{\sigma}=\sum_i\sigma_i$. Let $\mu$ be a probability distribution on $\X$, and $\mu\br{x}$ represent the probability of $x\in\X$ according to $\mu$. Let $X$ be a random variable distributed according to $\mu$. We use the same symbol to represent a random variable and its distribution whenever it is clear from the context. The expectation of a function $f$ on $\X$ is defined as
\[\expec{}{f(X)}=\expec{\mathbf{x}\sim X}{f(\mathbf{x})}=\sum_{x\in\X}\prob{X=x}\cdot f\br{x}=\sum_x\mu\br{x}\cdot f\br{x},\]
where $\mathbf{x}\sim X$ represents that $\mathbf{x}$ is drawn according to $X$. For any two distributions $\mu$ and $\nu$, $\br{\mathbf{x},\mathbf{y}}\sim\mu\otimes\nu$ represents that $\mathbf{x}$ and $\mathbf{y}$ are drawn from $\mu$ and $\nu$, independently. For two distributions $p$ and $q$, the $\ell_1$-distance between $p$ and $q$ is defined to be
\[\onenorm{p-q}=\sum_x\abs{p\br{x}-q\br{x}}.\]

In this paper, the lower-cased letters in bold $\mathbf{x},\mathbf{y},\cdots$ are reserved for random variables. The capital letters in bold, $\mathbf{P},\mathbf{Q},\ldots$ are reserved for random operators defined below.

§.§ Quantum mechanics

We briefly review the formalism of quantum mechanics over a finite dimensional system. For a more thorough treatment, readers may refer to [65, 84]. Given a quantum system $A$, it is associated with a finite dimensional Hilbert space, which, by abuse of notation, is also denoted by $A$. We denote by $\M\br{A}$ and $\H\br{A}$ the set of all linear operators and the set of all Hermitian operators in the space, respectively. The identity operator in $A$ is denoted by $\id_A$.  If the dimension of $A$ is $m$, then we write $\M\br{A}=\M_m$, $\H\br{A}=\H_m$ and $\id_A=\id_m$. The subscripts may be dropped whenever it is clear from the context. A quantum state in the quantum system $A$ is represented by a density operator $\rho_A$, a positive semidefinite operator over the Hilbert space $A$ with unit trace. We denote by $\D\br{A}$ the set of all density operators in $A$. A quantum state is pure if the density operator is a rank-one projector $\ketbra{\psi}$, which is also represented by $|ψ⟩$ for convenience. Composite quantum systems are associated with the {\em (Kronecker) tensor product space} of the underlying spaces, i.e., for the quantum systems $A$ and $B$, the composition of the two systems are represented by $A⊗B$ with the sets of the linear operators, the Hermitian operators and the density operators denoted by $A⊗B$, $A⊗B$ and $A⊗B$, respectively. We sometimes use the shorthand $AB$ for $A⊗B$. The sets of the linear operators and the Hermitian operators in the composition of $n$ $m$-dimensional Hilbert spaces are denoted by $_m^⊗n$ and  $_̋m^⊗n$, respectively. With a slight abuse of notations, we assume that $_m^⊗n=$ and $_̋m^⊗n=$ when $n=0$. A {\em quantum channel} from the input system $A$ to the output system $B$ is represented by a {\em completely positive, trace-preserving linear map} (CPTP map).  The set of all quantum channels from a system $A$ to a system $B$ is denoted by $ŁA,B$. A quantum channel in $ŁA,B$ is {\em unital} if it maps $𝕀_A$ to $𝕀_B$. A {\em quantum operator} on $A$ is a channel with both the input system and the output system being $A$. The set of the quantum operators on $A$ is denoted by $ŁA$. An important operation on a composite system $A⊗B$ is the {\em partial trace} $_B·$ which effectively derives the marginal state of the subsystem $A$ from the quantum state $ρ_AB$.  The partial trace is given by \[\Tr_B\rho_{AB}=\sum_i\br{\id_A\otimes\bra{i}}\rho_{AB}\br{\id_A\otimes\ket{i}}\] where $|i⟩$ is an orthonormal basis in $B$. The partial trace is a valid quantum channel in $ŁA⊗B, A$. Note that the action is independent of the choices of basis $|i⟩$, so we unambiguously write $ρ_A=_Bρ_AB$. In this paper, we may also apply the partial trace to an arbitrary operator in $A⊗B$. A pure state evolution on a system $A$ with a state $|ψ⟩$ is represented by a unitary operator $U^A$, denoted by $U^A|ψ⟩$.  An evolution on the register $B$ of a state $|ψ⟩_AB$ under the action of a unitary $U^B$  is represented by $𝕀^A⊗U^B|ψ⟩_AB$.  The superscripts and the subscripts might be dropped whenever it is clear from the context. A {\em quantum measurement} is represented by a {\em positive-operator valued measure} (POVM), which is a set of positive semidefinite operators $M_1,…, M_n$ satisfying $∑_i=1^nM_i=𝕀$, where $n$ is the number of possible measurement outcomes. Suppose the state of the quantum system is $ρ$. The probability that it outputs $i$ is $M_iρ$. In this paper, we use $M⃗=M_1,…, M_n$ to represent an ordered set of operators. We say $M⃗=M_1,…, M_n$ is a POVM if for each i $M_i≥0$ is a POVM element with the corresponding output $i$ and $∑_i M_i=𝕀$. We say $M⃗$ is a {\em sub-POVM} if $M_i≥0$ for $1≤i≤n$ and  $∑_i=1^n M_i≤𝕀$.

In this paper, we need the following fact.
\begin{fact}\label{fac:cauchyschwartz}
Given registers $A, B$, operators $P\in\H\br{A}, Q\in\H\br{B}$ and a bipartite state $\psi_{AB}$, it holds that
\begin{enumerate}
\item $\Tr\br{\br{P\otimes\id_B}\psi_{AB}}=\Tr P\psi_A$;

\item $\abs{\Tr\br{\br{P\otimes Q}\psi_{AB}}}\leq\br{\Tr P^2\psi_A}^{1/2}\cdot\br{\Tr Q^2\psi_B}^{1/2}$.
\end{enumerate}
\end{fact}

\begin{proof}
Item 1 follows from definitions.

For item 2, by Cauchy-Schwarz inequality, we have
\begin{align*}
&\abs{\Tr\br{\br{P\otimes Q}\psi_{AB}}}\\
=&\abs{\Tr\br{\sqrt{\psi_{AB}}\br{P\otimes \id}\br{\id\otimes Q}\sqrt{\psi_{AB}}}}\\
\leq&\br{\Tr\br{P\otimes \id}^2\psi_{AB}}^{1/2}\cdot\br{\Tr \br{\id\otimes Q}^2\psi_{AB}}^{1/2}\\
=&\br{\Tr P^2\psi_A}^{1/2}\cdot\br{\Tr Q^2\psi_B}^{1/2}\quad\quad\mbox{(item 1)}
\end{align*}
\end{proof}

\subsection{Gaussian spaces}\label{subsec:gaussian}

For $p≥1$ and any integer $n>0$, let $γ_n$ represent a standard $n$-dimensional normal distribution. A function $f:^n→$ is in $L^p,γ_n$ if \[\int_{\reals^n}\abs{f(x)}^p\gamma_n\br{dx}<\infty.\] All the functions considered in this paper are in $L^p,γ_n$ for all $p≥1$ unless otherwise stated. We say $f∈L^p,γ_n$ if $fx∈$ for all $x$. We equip $L^2,γ_n$ with an inner product \[\innerproduct{f}{g}_{\gamma_n}=\expec{\mathbf{x}\sim\gamma_n}{\conjugate{f\br{\mathbf{x}}}g\br{\mathbf{x}}}.\] Given $p≥1$ and $f∈L^p,γ_n$, the {\em $p$-norm} of $f$ is defined to be \[\norm{f}_p=\br{\int_{\reals^n}\abs{f(x)}^p\gamma_n\br{dx}}^{\frac{1}{p}}.\] Then $ff=f^2$. The set of {\em Hermite polynomials} forms an orthonormal basis in $L^2,γ_1$ with respect to the inner product $··_γ_1$. The Hermite polynomials $H_r:→$ for $r∈ℤ_≥0$ are defined as
\begin{equation}\label{eqn:hermitebasis}
H_0\br{x}=1; H_1\br{x}=x; H_r\br{x}=\frac{(-1)^r}{\sqrt{r!}}e^{x^2/2}\frac{d^r}{dx^r}e^{-x^2/2}.
\end{equation}
For any $σ∈σ_1,…,σ_n∈ℤ_≥0^n$, define
$H_σ:^n→$ as \begin{equation}\label{eqn:hermite}
\end{equation}
The set $H_σ:σ∈ℤ_≥0^n$ forms an orthonormal basis in $L^2,γ_n$. Every function $f∈L^2,γ_n$ has an {\em Hermite expansion}  as
$$f\br{x}=\sum_{\sigma\in\mathbb{Z}_{\geq 0}^n}\widehat{f}\br{\sigma}\cdot H_{\sigma}\br{x},$$
where $fσ$'s are the {\em Hermite coefficients} of $f$, which can be obtained by $fσ=H_σf_γ_n$. Recall that $wtσ=∑_i=1^nσ_i$ for $σ∈ℤ_≥0^n$. The degree of $f$ is defined to be \[\deg\br{f}=\max\set{\mathrm{wt}\br{\sigma}:~\widehat{f}\br{\sigma}\neq 0}.\]

Just as in Fourier analysis, we have {\em Parseval's identity}, that is, \[\twonorm{f}^2=\sum_{\sigma\in\mathbb{Z}_{\geq 0}^n}\abs{\widehat{f}\br{\sigma}}^2.\]

We say $f∈L^2,γ_n$ is {\em multilinear} if $fσ=0$ for $σ∉0,1^n$.

\begin{definition}\label{def:influencegaussian}
Given a function $f\in L^2\br{\complex,\gamma_n}$,
the {\em variance} of $f$ is defined to be
\begin{equation}\label{eqn:variance}
\var{f}=\expec{\mathbf{x}\sim \gamma_n}{\abs{f\br{\mathbf{x}}-\expec{}{f}}^2}.
\end{equation}
For any set $S\subseteq[n]$, the {\em conditional variance} $\var{f\br{\mathbf{x}}|\mathbf{x}_S}$ is defined to be
\begin{equation}\label{eqn:conditionalvariance}
\var{f\br{\mathbf{x}}|\mathbf{x}_S}=\expec{\mathbf{x}\sim \gamma_n}{\abs{f\br{\mathbf{x}}-\expec{}{f\br{\mathbf{x}}|\mathbf{x}_S}}^2\text{\Large$\mid$}\mathbf{x}_S}.
\end{equation}
The {\em influence} of the $i$-th coordinate(variable) on $f$, denoted by $\influence_i\br{f}$, is defined by
\begin{equation}\label{eqn:influencegaussian}
\influence_i\br{f}=\expec{\mathbf{x}\sim \gamma_n}{\var{f\br{\mathbf{x}}|\mathbf{x}_{-i}}}.
\end{equation}
The {\em total influence} of $f$ is defined by \[\influence\br{f}=\sum_i\influence_i\br{f}.\]
\end{definition}
The following fact summarizes the basic properties of variance and influence. Readers may refer to~[66] for a thorough treatment.
\begin{fact}\label{fac:influencegaussian}~[66, 62]
Given $f\in L^2\br{\complex,\gamma_n}$, it holds that
\begin{enumerate}
\item $\widehat{f}\br{\sigma}\in \reals$ if $f\in L^2\br{\reals,\gamma_n}$;
\item $\var{f}=\sum_{\sigma\neq 0^n}\abs{\widehat{f}\br{\sigma}}^2\leq\twonorm{f}^2$;
\item $\influence_i\br{f}=\sum_{\sigma:\sigma_i\neq 0}\abs{\widehat{f}\br{\sigma}}^2$, and hence for all $i$, $\influence_i\br{f}\leq\var{f}$;
\item $\influence\br{f}=\sum_{\sigma}\abs{\sigma}\abs{\widehat{f}\br{\sigma}}^2$;
\item $\influence\br{f}\leq\deg\br{f}\var{f}$.
\end{enumerate}
\end{fact}

\begin{definition}\label{def:ornstein}
Given $0\leq\rho\leq 1$ and $f\in L^2\br{\complex,\gamma_n}$, we define the Ornstein-Uhlenbeck operator $U_{\rho}$ to be
\[U_{\rho}f\br{z}=\expec{\mathbf{x}\sim \gamma_n}{f\br{\rho z+\sqrt{1-\rho^2}\mathbf{x}}}.\]
\end{definition}

\begin{fact}\label{fac:gaussiannoisy}~\cite[Page 338, Proposition 11.37]{Odonnell08}
For any $0\leq\rho\leq 1$ and $f\in L^2\br{\complex,\gamma_n}$, it holds that
\[U_{\rho}f=\sum_{\sigma\in\mathbb{Z}_{\geq0}^n}\widehat{f}\br{\sigma}\rho^{\wt{\sigma}}H_{\sigma}.\]
\end{fact}

% We will work on vector-valued functions as well. For any vector $v\in\complex^k$, the norm of $v$ is defined to be $\norm{v}=\sum\br
%{\abs{v_i}^2}^{1/2}$. For any function $f:\reals^n\rightarrow\reals^k$ and $\sigma\in\mathbb{Z}_{\geq 0}^n$, we will write $f=\br{f_1,\ldots, f_k}$, where $f_i:\reals\rightarrow\reals$  is the $i$-th coordinate of the output of $f$. That is, $f_i\br{x}=\br{f(x)}_i$ for any $x\in\reals$. we use $\widehat{f}\br{\sigma}$ to denote $\br{\widehat{f_1}\br{\sigma},\ldots,\widehat{f_k}\br{\sigma}}$. The norm $\twonorm{f}^2=\expec{\mathbf{x}\sim\gamma_n}{\norm{f\br{\mathbf{x}}}^2}=\sum_{i=1}^k\twonorm{f_i}^2=\sum_{\sigma\in\mathbb{Z}_{\geq 0}^n}\norm{\widehat{f}\br{\sigma}}^2$.  Also, the degree of $f$ is defined to be $\deg\br{f}=\max_{i\in[k]}\deg\br{f_i}$. Again, all vector-valued functions with domain $\reals^n$ will be such that each coordinate is in $L^2\br{\gamma_n}$ unless explicitly mentioned.

Given $p≥1$, a {\em vector-valued function} $f=f_1,…,f_k:^n→^k$ is in $L^p^k,γ_n$ if $f_i∈L^p,γ_n$ for all $i$. It is in $L^p^k,γ_n$ if $f_i∈L^p,γ_n$ for all $i$.  For any $f,g∈L^2^k,γ_n$, the inner product of $f$ and $g$ is defined to be \[\innerproduct{f}{g}_{\gamma_n}=\sum_{t=1}^k\innerproduct{f_t}{g_t}_{\gamma_n}.\] The $p$-norm of $f$ is \[\norm{f}_p=\br{\sum_{t=1}^k\norm{f_t}_p^p}^{1/p}.\]

For any $f∈L^2^k,γ_n$, the Hermite coefficients of $f$ are the vectors  \[\widehat{f}\br{\sigma}=\br{\widehat{f_1}\br{\sigma},\ldots,\widehat{f_k}\br{\sigma}}.\] The degree of $f$ is \[\deg\br{f}=\max_t\deg\br{f_t}.\] We say $f$ is multilinear if $f_i$ is multilinear for $1≤i≤k$. The variance of $f$ is \[\var{f}=\sum_t\var{f_t}.\] The influence of the $i$-th coordinate (variable) on $f$ is \[\influence_i\br{f}=\sum_t\influence_i\br{f_t}.\] The total influence of $f$ is \[\influence\br{f}=\sum_i\influence_i\br{f}.\]
The action of Ornstein-Uhlenbeck operator on $f$ is defined to be \[U_{\rho}f=\br{U_{\rho}f_1,\ldots, U_{\rho}f_k}.\]

For any vector $v∈^k$, the norm of $v$ is defined to be \[\norm{v}_2=\sqrt{\sum_{i=1}^k\abs{v_i}^2}.\]

\cref{fac:influencegaussian} and \cref{fac:gaussiannoisy} can be directly generalized to vector-valued functions.
\begin{fact}\label{fac:vecfun}
Given $f\in L^2\br{\complex^k,\gamma_n}$ and $0\leq\rho\leq 1$, it holds that
\begin{enumerate}
\item $\widehat{f}\br{\sigma}\in \reals^k$ if $f\in L^2\br{\reals^k,\gamma_n}$;
\item $\var{f}=\sum_{\sigma\neq 0^n}\norm{\widehat{f}\br{\sigma}}_2^2\leq\twonorm{f}^2$;
\item $\influence_i\br{f}=\sum_{\sigma:\sigma_i\neq 0}\norm{\widehat{f}\br{\sigma}}_2^2$, and hence for all $i$, $\influence_i\br{f}\leq\var{f}$;
\item $\influence\br{f}=\sum_{\sigma}\abs{\sigma}\cdot\twonorm{\widehat{f}\br{\sigma}}^2$;
\item $\influence\br{f}\leq\deg\br{f}\var{f}$;
\item $U_\rho f=\sum_{\sigma\in\mathbb{Z}_{\geq 0}^n}\widehat{f}\br{\sigma}\rho^{\wt{\sigma}}H_{\sigma}$.

\end{enumerate}
\end{fact}

For any $0≤ρ≤1$, $_ρ$ represents a  $ρ$-correlated Gaussian distribution, which is a  $2$-dimensional Gaussian distribution \[\br{X,Y}\sim N\br{\begin{pmatrix}
0 \\
\end{pmatrix},\begin{pmatrix}
1 & \rho \\
\rho & 1
\end{pmatrix}}.\] Namely, the marginal distributions $X$ and $Y$ are distributed according to $γ_1$ and $XY=ρ$.

\subsection{Matrix spaces and random matrix spaces}\label{subsec:matrixspace}
For a matrix $M$, with a slight abuse of notations, we use $M_i,j$ or $Mi,j$ to represent the $i,j$-th entry of $M$ whichever is convenient.

For $1≤p≤∞$ the $p$-norm of $M$ is defined to be \[\norm{M}_p=\br{\sum_{i=1}^{\min\set{m,n}}s_i\br{M}^p}^{1/p},\] where $s_1M,s_2M,…$ are the singular values of $M$ sorted in non-increasing order.  $M=M_∞=s_1M$ when $p=∞$. It is easy to verify that $M_p≤M_q$ if $p≥q$.  For $m=n$, the {\em normalized $p$-norm} of $M$ is defined as
\begin{equation}\label{eqn:nnormdef}
\nnorm{M}_p=\br{\frac{1}{m}\sum_{i=1}^ms_i\br{M}^p}^{1/p}
\end{equation}
and $M=M_∞=s_1M$. We have $M_p≥M_q$ if $p≥q$. For any $M∈_̋m$, $λ_1M,…,λ_mM$ represents the eigenvalues of $M$ in non-increasing order and $M=√(M^†M)$.

For a Hermitian matrix $X$, suppose it has a spectral decomposition $U^†ΛU$, where $U$ is unitary and $Λ$ is diagonal. Define
\begin{equation}\label{eqn:geq0def}
\pos{X}= U^{\dagger}\pos{\Lambda} U
\end{equation}
where \pos{\Lambda} is diagonal and $Λ_ii=Λ_ii$ if $Λ_ii≥0$, and $Λ_ii=0$ otherwise. Let $X$ be the {\em Moore-Penrose inverse} of $X$. Namely,
\begin{equation}\label{eqn:penrosedef}
\pinv{X}= U^{\dagger}\pinv{\Lambda} U
\end{equation}
where \pinv{\Lambda} is diagonal and $Λ_ii=Λ_ii^-1$ if $Λ_ii0$, and $Λ_ii=0$ otherwise.

Given two matrices $A, B$ of the same dimension, the {\em Hadamard product} of $A$ and $B$ is $A∘B$, where $A∘B_i,j= A_i,j·B_i,j$.
The {\em anticommutator} of $A$ and $B$ is defined to be $AB=AB+BA$.
Given $P,Q∈_m$, we define
\begin{equation}\label{eqn:innerproduct}
\innerproduct{P}{Q}=\frac{1}{m}\Tr~P^{\dagger}Q.
\end{equation}

\begin{fact}\label{fac:innerproduct}
$\innerproduct{\cdot}{\cdot}$ is an inner product. $\br{\innerproduct{\cdot}{\cdot},\M_m}$ forms a Hilbert space of dimension $m^2$. For any $M\in\M_m$, $\nnorm{M}_2^2=\innerproduct{M}{M}$.
\end{fact}

We say $_0,…,_m^2-1$ is a {\em standard orthonormal basis} in $_m$, if  it is an orthonormal basis with all elements being Hermitian and $_0=𝕀_m$.

\begin{fact}\label{fac:unitarybasis}
Given an orthonormal basis $\B=\set{\B_0,\ldots,\B_{m^2-1}}$, the set \linebreak $\B'=\set{\B'_0,\ldots,\B'_{m^2-1}}$ is also an orthonormal basis in $\M_m$ if and only if there exists an $\br{m^2}\times \br{m^2}$ unitary matrix $U$ with both rows and columns indexed by $[m^2]_{\geq 0}$ such that
\[\B'_i=\sum_{j=0}^{m^2-1}U_{i,j}\B_j\] for all
$0\leq i\leq m^2-1$. Moreover, if $\B$ is a standard orthonormal basis, the set $\B'$ is also a standard orthonormal basis in $\M_m$ if and only if $U$ is an orthogonal matrix and it satisfies $U_{0,j}=\delta_{0,j}$ for $0\leq j\leq m^2-1$.
\end{fact}

\begin{fact}\label{fac:paulimutiplecopy}
Let $\set{\B_i}_{i=0}^{m^2-1}$ be a standard orthonormal basis in $\M_m$, then
\[\set{\B_{\sigma}=\otimes_{i=1}^n\B_{\sigma_i}}_{\sigma\in[m^2]_{\geq 0}^n}\]
is a standard orthonormal basis in $\M_m^{\otimes n}$.
\end{fact}

The following lemma guarantees the existence of standard orthonormal bases.
\begin{lemma}\label{lem:paulibasis}
For any integer $m\geq 2$, there exists a standard orthonormal basis in $\M_m$.
\end{lemma}
\begin{proof}
Consider the space $\br{\H_m,\reals}$ i.e., the space of Hermitian matrices over the real number field, with respect to the inner product $\innerproduct{P}{Q}=\frac{1}{m}\Tr P^{\dagger}Q$. As the inner product of two Hermitian matrices is real, $\br{\H_m,\reals}$ forms a real Hilbert space. Apparently the dimension of $\br{\H_m,\reals}$ is $m^2$ and $\id_m\in\H_m$ with $\innerproduct{\id_m}{\id_m}=1$. Thus, there exists an orthonormal basis $\set{\B_i}_{0\leq i< m^2}$ in $\br{\H_m,\reals}$ with $\B_0=\id$. Note that $\set{\B_i}_{0\leq i< m^2}$ is still an orthonormal set in $\M_m$. Moreover, the dimension of $\br{\M_m,\complex}$, i.e., the space of $m\times m$ matrices over the complex number field, is also $m^2$. Thus, $\set{\B_i}_{0\leq i< m^2}$ forms a standard orthonormal basis in $\M_m$.
%	It is easy to verify that
%	the set $$\set{\sqrt{m}\cdot\ketbra{j}}_{0\leq j\leq  m-1}\cup\set{\sqrt{m/2}\br{\ketbratwo{j}{k}+\ketbratwo{k}{j}}}_{0\leq j<k\leq m-1}\cup\set{\sqrt{m/2}\br{\mathrm{i}\cdot \ketbratwo{j}{k}-\mathrm{i}\cdot\ketbratwo{k}{j}}}_{0\leq j<k\leq m-1}$$ forms an orthonormal basis in $\M_m$. Let's denote it by $\set{\A_1,\ldots, \A_{m^2}}$. Suppose
%	\[\id_m=\sum_{i=1}^{m^2} x_i\A_i.\]
%	Then $x=\br{x_1,\ldots, x_{m^2}}$ is a unit vector in $\reals^{m^2}$. Let $\br{x^{(0)},\ldots,x^{(m^2-1)}}$ be a set of orthonormal vectors in $\reals^{m^2}$ with $x^{(0)}=x$. Define $\B_i=\sum_{j=1}^{m^2}x^{(i)}_j\A_j$. Then $\set{\B_i}_{0\leq i\leq m^2-1}$ is a standard orthonormal basis in $\M_m$ by \cref{fac:unitarybasis}.
\end{proof}

Given a standard orthonormal basis $=_i_i=0^m^2-1$ in $_m$, every matrix $M∈_m^⊗n$ has a {\em Fourier expansion} with respect to the basis $$ given by
\[M=\sum_{\sigma\in[m^2]_{\geq 0}^{n}}\widehat{M}\br{\sigma}\B_{\sigma},\]
where $Mσ$'s are the {\em Fourier coefficients} of $M$ with respect to the basis $$. They can be obtained as $Mσ=_σM$. The basic properties of $Mσ$'s are summarized in the following fact, which can be easily derived from the orthonormality of $_σ_σ∈[m^2]_≥0^n$.
\begin{fact}\label{fac:basicfourier}
Given a standard orthonormal basis $\set{\B_i}_{i=0}^{m^2-1}$ in $\M_m$ and $M,N\in\M_m$, it holds that
\begin{enumerate}
\item $\widehat{M}\br{\sigma}$'s are real for all $\sigma\in[m^2]_{\geq 0}$ if and only if $M$ is Hermitian;
\item $\innerproduct{M}{N}=\innerproduct{\id}{M^{\dagger}N}=\innerproduct{MN^{\dagger}}{\id}=\sum_{\sigma}\conjugate{\widehat{M}\br{\sigma}}\widehat{N}\br{\sigma}$;
\item $\nnorm{M}_2^2=\innerproduct{M}{M}=\innerproduct{M^{\dagger}M}{\id}=\innerproduct{\id}{M^{\dagger}M}=\sum_{\sigma}\abs{\widehat{M}\br{\sigma}}^2$;
\item $\innerproduct{\id}{M}=\widehat{M}\br{0}$.
\end{enumerate}
\end{fact}
The {\em variance} of a matrix $M∈_m$ is defined to be  $$\var{M}=\innerproduct{M}{M}-\innerproduct{M}{\id}\innerproduct{\id}{M}.$$
The following lemma is easily verified.
\begin{lemma}\label{lem:variance}
Given a standard orthonormal basis $\set{\B_i}_{i=0}^{m^2-1}$ in $\M_m$ and $M\in\M_m$, it holds that
\[\var{M}=\sum_{\sigma\neq 0}\abs{\widehat{M}\br{\sigma}}^2.\]
\end{lemma}

\begin{definition}
Let $\B=\set{\B_i}_{i=0}^{m^2-1}$ be a standard orthonormal basis in $\M_m$, $P,Q\in\M_m^{\otimes n}$ and a subset $S\subseteq[n]$.
\begin{enumerate}
\item The degree of $P$ is defined to be \[\deg P=\max\set{\abs{\sigma}:\widehat{P}\br{\sigma}\neq 0}.\]
Recall that $\abs{\sigma}$ represents the number of nonzero entries of $\sigma$.
\item For any $S\subseteq[n]$, \[P_S=\frac{1}{m^{|S^c|}}\Tr_{S^c}P.\]
\item For any $S\subseteq[n]$,  \[\mathrm{Var}_S[P]=\br{P^{\dagger}P}_{S^c}-\br{P_{S^c}}^{\dagger}\br{P_{S^c}}.\] If $S=\set{i}$, we use $\mathrm{Var}_i[P]$ in short.
\item For any $i\in[n]$, \[\influence_i\br{P}=\innerproduct{\id}{\mathrm{Var}_i[P]}.\]
\item \[\influence\br{P}=\sum_i\influence_i\br{P}.\]
\end{enumerate}
\end{definition}

With the notion of degrees, we define the low-degree part and the high-degree part of an operator.

\begin{definition}\label{def:lowdegreehighdegree}
Given integers $m,t>0$, a standard orthonormal basis $\B=\set{\B_i}_{i=0}^{m^2-1}$ in $\M_m$ and $P\in\M_m^{\otimes n}$, we define
\[P^{\leq t}=\sum_{\sigma\in[m^2]_{\geq 0}^n:\abs{\sigma}\leq t}\widehat{P}\br{\sigma}\B_{\sigma};\]
\[P^{\geq t}=\sum_{\sigma\in[m^2]_{\geq 0}^n:\abs{\sigma}\geq t}\widehat{P}\br{\sigma}\B_{\sigma}\]
\[P^{=t}=\sum_{\sigma\in[m^2]_{\geq 0}^n:\abs{\sigma}=t}\widehat{P}\br{\sigma}\B_{\sigma};\]
where $\widehat{P}\br{\sigma}$'s are the Fourier coefficients of $P$ with respect to the basis $\B$.
%It is proved in~\cite{Yao:2020} that the degree of $P$ is independent of the choices of the basis. Moreover, $P^{\leq t}, P^{\geq t}$ and $P^{=t}$ are also independent of the choices of the basis.
\end{definition}

\begin{lemma}\label{lem:pt}
The degree of $P$ is independent of the choices of bases. Moreover, $P^{\leq t}, P^{\geq t}$ and $P^{=t}$ are also independent of the choices of bases.
\end{lemma}

\begin{proof}
Let $\set{\B_{\sigma}}_{\sigma\in[m^2]_{\geq 0}}$ and $\set{\B'_{\sigma}}_{\sigma\in[m^2]_{\geq 0}}$ be two standard orthonormal bases in $\M_m$. From \cref{fac:unitarybasis},  there exists an $\br{m^2-1}\times \br{m^2-1}$ orthogonal matrix $U$ satisfying that \[\B_{\sigma}=\sum_{\sigma'=1}^{m^2-1}U_{\sigma,\sigma'}\B'_{\sigma'}\] for any $\sigma\in[m^2-1]$. Suppose $P=P^{=t}$ with respect to the basis $\set{\B_{\sigma}}_{\sigma\in[m^2]_{\geq 0}}$. By linearity, we may assume that $P=\B_{\sigma}=\bigotimes_{i=1}^n\B_{\sigma_i}$  without loss of generality. It is easy to verify that each term in the expansion of $P$ in the basis $\set{\B_i'}_{i=0}^{m^2-1}$ is also of degree $\abs{\sigma}$. The result follows.
\end{proof}

\begin{lemma}\label{lem:partialvariance}
Given $P\in\M_m^{\otimes n}$, a standard orthonormal basis $\B=\set{\B_i}_{i=0}^{m^2-1}$ in $\M_m$ and a subset $S\subseteq[n]$, it holds that
\begin{enumerate}
\item $P_S=\innerproduct{\id}{P}_{S^c}=\sum_{\sigma:\sigma_{S^c}=\mathbf{0}}\widehat{P}\br{\sigma}\B_{\sigma_S}$, $\nnorm{P_S}_2\leq\nnorm{P}_2$;
\item $\innerproduct{\id_{S^c}}{\mathrm{Var}_S[P]}=\sum_{\sigma:\sigma_S\neq\mathbf{0}}\abs{\widehat{P}\br{\sigma}}^2$;
\item $\influence_i\br{P}=\sum_{\sigma:\sigma_i\neq0}\abs{\widehat{P}\br{\sigma}}^2$;
\item $\influence\br{P}=\sum_{\sigma}\abs{\sigma}\abs{\widehat{P}\br{\sigma}}^2\leq\deg P\cdot\nnorm{P}^2_2$.
\end{enumerate}
\end{lemma}
\begin{proof}
\begin{enumerate}
\item For the equality,\[P_S=\frac{1}{m^{|S^c|}}\sum_{\sigma}\widehat{P}\br{\sigma}\Tr_{S^c}\B_{\sigma}=\text{RHS}.\]

%For the second inequality, it suffices to show that $\norm{P_{-i}}\leq\norm{P}$ for any $i\in[n]$. Without loss of generality, we may assume $i=1$. For any unit vector $\ket{v}$
%		\[\bra{v}P_{-1}\ket{v}=\frac{1}{m}\bra{v}\br{\Tr_{\set{1}}P}\ket{v}=\Tr P\br{\frac{\id_m}{m}\otimes\ketbra{v}}\leq\norm{P},\]
%		where the last inequality is from the fact that $\abs{\Tr PQ}\leq\norm{P}\onenorm{Q}$ .
For the inequality,
\[\nnorm{P_S}^2_2=\sum_{\sigma:\sigma_{S^c}={\mathbf{0}}}\abs{\widehat{P}\br{\sigma}}^2\leq\sum_{\sigma}\abs{\widehat{P}\br{\sigma}}^2=\nnorm{P}^2_2,\]
where both equalities are from \cref{fac:basicfourier} item 3.

\item
From  item 1,
\[\br{P^{\dagger}P}_{S^c}=\sum_{\sigma,\sigma'}\conjugate{\widehat{P}\br{\sigma}}\widehat{P}\br{\sigma'}\br{\B_{\sigma}\B_{\sigma'}}_{S^c}=\sum_{\sigma,\sigma':\sigma_S=\sigma'_S}\conjugate{\widehat{P}\br{\sigma}}\widehat{P}\br{\sigma'}\B_{\sigma_{S^c}}\B_{\sigma'_{S^c}}.\]
\[\br{P_{S^c}}^{\dagger}\br{P_{S^c}}=\sum_{\sigma,\sigma':\sigma_S=\sigma'_S=\mathbf{0}}\conjugate{\widehat{P}\br{\sigma}}\widehat{P}\br{\sigma'}\B_{\sigma_{S^c}}\B_{\sigma'_{S^c}}.\]
\begin{eqnarray*}
\innerproduct{\id_{S^c}}{\mathrm{Var}_S[P]}=\sum_{\sigma:\sigma_S\neq\mathbf{0}}\abs{\widehat{P}\br{\sigma}}^2.
\end{eqnarray*}
\item It follows from item 2 and the definition of $\influence_i\br{\cdot}$.
\item It can be verified by a direct calculation.
\end{enumerate}
\end{proof}

\begin{definition}\label{def:efronstein}\br{\textbf{Efron-Stein decomposition}} Given integers $n,d>0$, an operator $P\in\M_m^{\otimes n}$, a standard orthonormal basis $\set{\B_i}_{i=0}^{m^2-1}$ and $S\subseteq[n]$, set \[P[S]=\sum_{\sigma\in[m^2]_{\geq 0}^n:\supp{\sigma}=S}\widehat{P}\br{\sigma}\B_{\sigma},\] where $\supp{\sigma}=\set{i\in[n]:\sigma_i>0}$. The Efron-Stein decomposition of $P$ is \[P=\sum_{S\subseteq[n]}P[S].\]
\end{definition}
Again, the definition of $P[S]$ is independent of the choices of the basis $_i_i=0^m^2-1$, followed by the same argument for \cref{lem:pt}.

The following proposition can be obtained from the orthogonality of $_i$'s.
\begin{proposition}\label{prop:enfronsteinortho}
Given integers $m,n>0$, $S\neq T\subseteq[n]$ and $P,Q\in\M_m^{\otimes n}$, it holds that $\innerproduct{P[S]}{Q[T]}=0$.
\end{proposition}
\begin{proposition}\label{prop:efronstein}
Given integers $m,n>0$,  $P\in\M_m^{\otimes n}$ and $S,T\subseteq[n], S\not\subseteq T$, it holds that
\[\Tr_{T^c}~P[S]=0.\]
\end{proposition}
\begin{proof}
\[\Tr_{T^c}~P[S]=\Tr_{T^c}~\br{\sum_{\sigma:\supp{\sigma}=S}\widehat{P}\br{\sigma}\B_{\sigma}}=0,\]
where the second equality holds because $S\cap T^c\neq\emptyset$.
\end{proof}

\begin{lemma}\label{lem:jointbasis}
Given $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, where $m_A$ and $m_B$  are the dimensions of $A$ and $B$, respectively, there exist standard orthonormal bases $\set{\X_{\alpha}}_{\alpha\in[m_A^2]_{\geq 0}}$ and $\set{\Y_{\beta}}_{\beta\in[m_B^2]_{\geq 0}}$ in  $\M\br{A}$ and $\M\br{B}$, respectively, such that
\[\Tr\br{\br{\X_{\alpha}\otimes\Y_{\beta}}\psi_{AB}}=\delta_{\alpha,\beta}c_{\alpha}\] for $\alpha\in[m_A^2]_{\geq 0},\beta\in[m_B^2]_{\geq 0}$ and $c_{\alpha}\geq 0$.
\end{lemma}

\begin{proof}
Let $\set{\A_{\alpha}}_{\alpha\in[m_A^2]_{\geq 0}}$ and $\set{\B_{\beta}}_{\beta\in[m_B^2]_{\geq 0}}$ be arbitrary standard orthonormal bases in $\M_{m_A}$ and $\M_{m_B}$, respectively. Let $\br{M_{\alpha,\beta}}_{\alpha\in[m_A^2]_{\geq 0},\beta\in[m_B^2]_{\geq 0}}$ be an $m_A^2\times m_B^2$ matrix, where
\[M_{\alpha,\beta}=\Tr\br{\br{\A_{\alpha}\otimes\B_{\beta}}\psi_{AB}}.\] Then $M$ is a real matrix of the form
\begin{equation}
1 & 0 & \cdots & 0 \\
0 & & &          &    \\
\raisebox{15pt}{\vdots}  & & \raisebox{15pt}{{\huge\mbox{{$M'$}}}}  & \\
0 &  & &
\end{pmatrix}.
\end{equation}
Let $M'=U^{\dagger}DV^{\dagger}$ be a singular value decomposition of $M'$ where $U, V$ are both orthogonal matrices and $D$ is a diagonal matrix.  For any $\alpha\in[m_A^2]_{\geq 0}$ and $\beta\in[m_B^2]_{\geq 0}$ set
\[\X_{\alpha}=\begin{cases}\sum_{\alpha'=1}^{m_A^2-1}U_{\alpha,\alpha'}\A_{\alpha'}~&\mbox{if $\alpha\neq 0$}\\
\id_{m_A}~&\mbox{otherwise},\end{cases}
\Y_{\beta}=\begin{cases}\sum_{\beta'=1}^{m_B^2-1}V_{\beta',\beta}\B_{\beta'}~&\mbox{if $\beta\neq 0$}\\
\id_{m_B}~&\mbox{otherwise}.\end{cases}.\]
From \cref{fac:unitarybasis}, $\set{\X_{\alpha}}_{\alpha=0}^{m_A^2-1}$ and $\set{\Y_{\beta}}_{\beta=0}^{m_B^2-1}$ are standard orthonormal bases in $\M\br{A}$ and $\M\br{B}$, respectively. Then
\[\Tr\br{\br{\X_{\alpha}\otimes\Y_{\beta}}\psi_{AB}}=\begin{cases}\br{UM'V}_{\alpha,\beta}=\delta_{\alpha,\beta}D_{\alpha,\alpha}~&\mbox{if $\alpha,\beta>0$,}\\ \delta_{\br{0,0},\br{\alpha,\beta}}~&\mbox{otherwise}.\end{cases}\]

\end{proof}
\subsection{Random operators}\label{subsec:randomoperators}
From the previous subsections, we see that the matrix space $_m^⊗n$ and Gaussian space $L^2, γ_n$ are both Hilbert spaces. In this subsection, we unify both spaces by random operators.

\begin{definition}\label{def:randomoperators}
Given $p\geq 1$, integers $h, n, m>0$, we say $\mathbf{P}$ is a random operator if it can be expressed as
\begin{equation}\label{eqn:randomoperatorexpansion}
\mathbf{P}=\sum_{\sigma\in[m^2]_{\geq 0}^h}p_{\sigma}\br{\mathbf{g}}\B_{\sigma},
\end{equation}
where $\set{\B_i}_{i=0}^{m^2-1}$ is a standard orthonormal basis in $\M_m$, $p_{\sigma}:\reals^n\rightarrow\complex$ for all $\sigma\in[m^2]_{\geq 0}^h$ and $\mathbf{g}\sim \gamma_n.$ $\mathbf{P}\in L^p\br{\M_m^{\otimes h},\gamma_n}$ if $p_{\sigma}\in L^p\br{\complex,\gamma_n}$ for all $\sigma\in[m^2]_{\geq 0}^h$. Moreover, $\mathbf{P}\in L^p\br{\H_m^{\otimes n},\gamma_n}$ if $p_{\sigma}\in L^p\br{\reals,\gamma_n}$. Define a vector-valued function \[p=\br{p_{\sigma}}_{\sigma\in[m^2]_{\geq 0}^h}:\reals^n\rightarrow\complex^{m^{2h}}.\] We say $p$ is the {\em associated vector-valued function} of $\mathbf{P}$ under the basis $\set{\B_i}_{i=0}^{m^2-1}$.
\end{definition}

The following is a generalization of the $p$-norm in $L^2_m^⊗h,γ_n$.

\begin{definition}\label{def:randop}\footnote{To clarify the potential ambiguity, we consider $\nnorm{\mathbf{P}}_p$ to be a random variable and use $N_p\br{\cdot}$ to represent the normalized $p$-norm of a random operator.}\label{def:randoperatorsbasic}
Given $p\geq 1$, integers $n,h>0, m>1$ and random operator $\mathbf{P}\in L^p\br{\M_m^{\otimes h},\gamma_n}$, the normalized $p$-norm of $\mathbf{P}$ is \[N_p\br{\mathbf{P}}=\br{\expec{}{\nnorm{\mathbf{P}}_p^p}}^{\frac{1}{p}}.\] The degree of $\mathbf{P}$, denoted by $\deg\br{\mathbf{P}}$, is \[\max_{\sigma\in[m^2]_{\geq 0}^h}\deg\br{p_{\sigma}}.\] We say $\mathbf{P}$ is multilinear if $p_{\sigma}\br{\cdot}$ is multilinear for all $\sigma\in[m^2]_{\geq 0}^h$.
\end{definition}

\begin{lemma}\label{lem:randoperator}
Given integers $n,h>0, m>1$, let $\mathbf{P}\in L^2\br{\M_m^{\otimes n},\gamma_h}$ with an  associated vector-valued function $p$ under a standard orthonormal basis. It holds that  $N_2\br{\mathbf{P}}=\twonorm{p}.$
\end{lemma}
\begin{proof}
\[N_2\br{\mathbf{P}}^2=\expec{}{\nnorm{\mathbf{P}}_2^2}=\expec{\mathbf{g}\sim \gamma_n}{\sum_{\sigma\in[m^2]_{\geq 0}^h}\abs{p_{\sigma}\br{\mathbf{g}}}^2}=\twonorm{p}^2,\]
where the second equality follows from \cref{fac:basicfourier} item 3.
\end{proof}
\begin{lemma}\label{lem:influencerandomoperator}
Given a multilinear random operator $\mathbf{P}\in L^2\br{\M_m^{\otimes h},\gamma_n}$ with degree $d$ and the associated vector-valued function $p$ under a standard orthonormal basis, it holds that
\[\influence\br{p}\leq \deg\br{\mathbf{P}}N_2\br{\mathbf{P}}^2.\]
\end{lemma}
\begin{proof}
\[\influence\br{p}\leq\deg\br{p}\var{p}\leq\deg\br{p}\twonorm{p}^2=\deg\br{\mathbf{P}}\twonorm{p}^2=\deg\br{\mathbf{P}}N_2\br{\mathbf{P}}^2,\]
where the first inequality follows from \cref{fac:vecfun} item 5; the second inequality follows from \cref{fac:vecfun} item 2; the first equality follows from the definition of the degree of a random operator; the second equality follows from \cref{lem:randoperator}.
\end{proof}

We say a pair of random operators $𝐏,𝐐∈L^p_m^⊗h,γ_n×L^p_m^⊗h,γ_n $ are {\em joint random operators} if the random variables $𝐠,𝐡$ in $𝐏,𝐐$ are drawn from a joint distribution $_ρ^⊗n$ for $0≤ρ≤1$.

\subsection{Miscellaneous}\label{subsec:misc}

Throughout this paper, functions $f:→$ are also viewed as maps $f:_̋m→_̋m$ defined as
\[f\br{P}=\sum_if\br{\lambda_i}\ketbra{v_i},\] where \[P=\sum_i\lambda_i\ketbra{v_i}\] is a spectral decomposition of $P$.

Given a closed convex set $\Delta\subseteq\reals^k$, we say a map $\R:\reals^k\rightarrow\reals^k$ is a rounding map of $\Delta$ if for any $x\in\reals^k$, $\R\br{x}$ is the element in $\Delta$ that is closest to $x$ in $\twonorm{\cdot}$ distance. The following well-known fact states that the rounding maps of closed convex sets are Lipschitz continuous with Lipschitz constant being $1$.

\begin{fact}\label{fac:rounding}\cite[Page 149, Proposition 3.2.1]{bertsekas2015convex}
Let $\Delta$ be a nonempty closed convex set in $\reals^k$ with the rounding map $\R$. It holds that
\[\twonorm{\R\br{x}-\R\br{y}}\leq\twonorm{x-y},\]
for any $x,y\in\reals^k$.

Thus, if $\Delta$ contains the element $\br{0,\ldots, 0}$, then $\R$ is a {\em contraction}. Namely, $\twonorm{\R\br{x}}\leq\twonorm{x}$ for any $x\in\reals^k$.
\end{fact}

%\highlight{We will use the following lemma in the proof of the main result.
%Let $P_1,\dots,P_t$ be satisfying that $\sum_{i=1}^tP_i=\id$, and $f$ be a unital linear map. Then
\section{Markov super-operators, noise operators and maximal correlation}\label{sec:markov}
%Given $\psi\in\D_m$ and $P,Q\in\M_m$, we define
%for any $P,Q\in\M_m$.

%The following fact can be easily verified.
%	$\innerproduct{\cdot}{\cdot}_{\psi}$ is an inner product and $\norm{\cdot}_{\psi}=\sqrt{\innerproduct{P}{P}_{\psi}}$ is a norm whenever $\psi$ is a positive definite density operator.
%The inner product defined in Eq.~\cref{eqn:innerproduct} can be viewed as the inner product above with $\psi=\frac{\id_m}{m}$, where $m$ is the dimension.
%For any integer $n>0$, $\psi^{\otimes n}$ induces an inner product in $\M_m^{\otimes n}$. To keep the notations short, the inner product is represented as
%\[\innerproduct{P}{Q}_{\psi}=\frac{1}{2}\Tr~\br{P^{\dagger}Q+QP^{\dagger}}\psi^{\otimes n},\]
%for $P,Q\in\M_m^{\otimes n}$.
%For any quantum state $\psi>0$ in $\M_m$, we denote the space induced by the inner product defined in Eq.~\cref{eqn:innerproduct} by $\br{\M_m,\psi}$. Note that $\norm{\id_m}_{\psi}=1$. Similar to \cref{subsec:matrixspace}, we say an orthonormal basis in $\br{\M_m,\psi}$ is standard if all the operators are Hermitian and it contains $\id$ as an element. The following lemma guarantees the existence of a standard orthonormal basis in $\br{\M_m,\psi}$.
%	For any integer $m>1$ and positive definite density operator $\psi\in\H_m$, there exists a standard orthonormal basis in $\br{\M_m,\psi}$.
%  The proof is close to the one of \cref{lem:paulibasis}. Consider the map $\lambda\br{\cdot,\cdot}:\H_m\times\H_m\rightarrow\reals$, which is defined to be $\lambda\br{P,Q}=\Tr~\br{PQ+QP}\psi$. It is easy to verify that $\lambda\br{\cdot,\cdot}$ is an inner product and $\br{\H_m,\lambda}$ over $\reals$ forms a real Hilbert space of dimension $m^2$. Note that $\lambda\br{\id_m,\id_m}=1$. Thus there exists an orthonormal basis $\set{\B_i}_{0\leq i\leq m^2-1}$ in $\br{\H_m,\lambda}$ with $\B_0=\id_m$. Further notice that $\lambda$ is identical to $\innerproduct{\cdot}{\cdot}_{\psi}$ in $\H_m$. Thus $\set{\B_i}_{0\leq i\leq m^2-1}$ is still an orthonormal set with respect to $\innerproduct{\cdot}{\cdot}_{\psi}$. Moreover, $\br{\M_m,\innerproduct{\cdot}{\cdot}_{\psi}}$ over $\complex$ is a Hilbert space of dimension $m^2$. Hence, $\set{\B_i}_{0\leq i\leq m^2-1}$ is a standard orthonormal basis in $\br{\M_m,\innerproduct{\cdot}{\cdot}_{\psi}}$.

%The Efron-Stein decomposition in \cref{def:efronstein} can be extended to $\br{\M_m,\psi}$ as well. Similar to \cref{lem:efronsteinortho}, the terms in Efron-Stein decompositions are orthogonal to each other with respect to the inner product $\innerproduct{\cdot}{\cdot}_{\psi}$.
\begin{definition}\label{def:markovoperator}
Given quantum systems $A$ and $B$ and a bipartite state $\psi_{AB}$,  we define a {\em Markov super-operator} $\T:\M\br{B}\rightarrow\M\br{A}$ as follows.
\[\Tr\br{\br{M^{\dagger}\otimes Q}\psi_{AB}}=\innerproduct{M}{\T\br{Q}},\]
for any $M\in\M\br{A}$ and $Q\in\M\br{B}$.
\end{definition}

\begin{lemma}\label{lem:markovoperator}
Given quantum systems $A$ and $B$ and a bipartite state $\psi_{AB}$,  $\T\br{Q}=m_A\Tr_B\br{\br{\id\otimes Q}\psi_{AB}}$.
\end{lemma}

\begin{proof}
By \cref{def:markovoperator}, $\T\br{Q}$ must satisfy that
\[m_A\Tr \br{M^{\dagger}\cdot\Tr_B\br{\br{\id\otimes Q}\psi_{AB}}}=\Tr M^{\dagger}\T\br{Q}\] for any $M\in\M\br{A}$. We conclude the result.
\end{proof}

\begin{lemma}\label{lem:markovtensor}
Given quantum systems $A$ and $B$ and a bipartite state $\psi_{AB}$,  let $\T_B:\M\br{B}\rightarrow\M\br{A}$ and $\T_{B^n}:\M\br{\B^n}\rightarrow\M\br{A^n}$ be the Markov super-operator from $\M\br{B}$ to $\M\br{A}$ and the one from $\M\br{B^n}$ to $\M\br{A^n}$ with the corresponding bipartite states $\psi_{AB}$ and $\psi_{AB}^{\otimes n}$, respectively.  Then $\T_{B^n}=\otimes_{i=1}^n\T_{B}$.
\end{lemma}
%\commentt{It's implicit in the proof, but I think the lemma statement should include the fact that $\phi^n$ is the state that you're using to define the Markov super-operator for systems $A^n$ and $B^n$.}
\begin{proof}
By the linearity of $\T_B$ and $\T_{B^{\otimes n}}$, it suffices to show $\T_{B^n}(Q)=\otimes_{i=1}^n\T_{B}\br{Q_i}$ when $Q=\otimes_{i=1}^nQ_i$. By \cref{lem:markovoperator}, we have
\begin{align*}
\T\br{Q}&=m_A^n\Tr_{B^n}\br{\br{\id_{A^n}\otimes Q}\psi_{AB}^{\otimes n}}\\
&=\bigotimes_{i=1}^n\br{m_A\Tr_B\br{\br{\id_A\otimes Q_i}\psi_{AB}}}\\
\end{align*}

\end{proof}

\begin{definition}\label{def:bonamibeckner}
Given a system $A$ of dimension $m$, $\rho\in[0,1]$, a noise operator $\Delta_{\rho}:\M\br{A}\rightarrow\M\br{A}$ on $\M(A)$ is defined as follows. For any $P\in\M\br{A}$,
\[\Delta_{\rho}\br{P}=\rho P+\frac{1-\rho}{m}\br{\Tr P}\cdot\id_m.\]
With a slight abuse of notations, the noise operator on  the space $\M\br{A^n}$, again denoted by $\Delta_{\rho}$, is defined as $\Delta_{\rho}=\Delta_{\rho}^{(1)}\cdot\Delta_{\rho}^{(2)}\cdots\Delta_{\rho}^{(n-1)}\cdot\Delta_{\rho}^{(n)}$, where $\Delta_{\rho}^{(i)}$ applies the noise operator $\Delta_{\rho}$ to the $i$'th register and keeps other registers untouched.
\end{definition}
The noise operators $\Delta_{\rho}$ are also called {\em depolarizing channels}~[65] in quantum information theory, which are also analogs of the {\em Bonami-Beckner operators} in Fourier analysis~[7, 15].

Recall that $\nnorm{\cdot}_p$ represents the normalized $p$-norm defined in \cref{eqn:nnormdef}.

\begin{lemma}\label{lem:bonamibecknerdef}
Given integers $d,n,m>0$, $\rho\in[0,1]$, a standard orthonormal basis of $\M_m$: $\B=\set{\B_i}_{i=0}^{m^2-1}$, the following holds.
\begin{enumerate}
\item For any $P\in\M_m^{\otimes n}$ with a Fourier expansion $P=\sum_{\sigma\in[m^2]_{\geq 0}^n}\widehat{P}\br{\sigma}\B_{\sigma}$, it holds that
\[\Delta_{\rho}\br{P}=\sum_{\sigma\in[m^2]_{\geq 0}^n}\rho^{\abs{\sigma}}\widehat{P}\br{\sigma}\B_{\sigma}.\]
\item For any $P\in\M_m^{\otimes n}$, $\nnorm{\Delta_{\rho}\br{P}}_2\leq \nnorm{P}_2$ and $\norm{\Delta_{\rho}\br{P}}\leq\norm{P}$.
\item If $P\geq0$, then $\Delta_{\rho}\br{P}\geq0$.
\end{enumerate}
\end{lemma}

\begin{proof}
Note that $\B_0=\id_m$. Item 1 follows from the definition directly.

For item 2,
%we define $\T^{\br{i}}_{\rho}$ be the operator on $\M_m^{\otimes n}$ which applies $\Delta_{\rho}$ to the $i$-th system and leaves other systems untouched. Then $\Delta_{\rho}=\Delta_{\rho}^{(n)}\circ\cdots\circ\T^{(1)}_{\rho}$. From item 1, we have
%	\begin{eqnarray*}
%		&&\Delta^{\br{i}}_{\rho}\br{P}=\sum_{\sigma:\sigma_i=0}\widehat{P}\br{\sigma}\B_{\sigma}+\rho\sum_{\sigma:\sigma_i\neq0}\widehat{P}\br{\sigma}\B_{\sigma}\\
%		&=&\rho P+\br{1-\rho}\sum_{\sigma:\sigma_i=0}\widehat{P}\br{\sigma}\B_{\sigma}=\rho P+\br{1-\rho}P_{-i}\otimes\B_0^{(i)},
%	\end{eqnarray*}
%	where $\B_0^{(i)}$ means that it is in the $i$-th register.
%	Note that the spectral norm of the first term is at most $\rho\norm{P}$. The spectral norm of the second term is at most $\br{1-\rho}\norm{P}$ by \cref{lem:partialvariance} item 1.
%	Hence $\norm{\Delta_{\rho}^{\br{i}}\br{P}}\leq\norm{P}$. Thus the first inequality in item 2 follows. To prove the second inequality,
\[\nnorm{\Delta_{\rho}\br{P}}_2^2=\sum_{\sigma\in[m^2]_{\geq 0}^n}\rho^{2\abs{\sigma}}\abs{\widehat{P}\br{\sigma}}^2\leq\sum_{\sigma\in[m^2]_{\geq 0}^n}\abs{\widehat{P}\br{\sigma}}^2=\nnorm{P}_2^2.\]
For the second inequality, in item 2,
%we prove it by the induction on $n$. For the base case $n=1$, we have  %The case that $n>1$ follows by induction.
%%\highlight{we prove by induction. For $n=1$,
%\[\norm{\Delta_{\rho}\br{P}}\leq \rho\norm{P}+\frac{1-\rho}{m}\abs{\Tr~P}\leq\rho\norm{P}+\br{1-\rho}\norm{P}=\norm P.\]
%where the last inequality is from the fact that $\abs{\Tr~AB}\leq\norm{A}\cdot\onenorm{B}$. For $n>1,$
note that $\Delta_{\rho}=\Delta_{\rho}^{(1)}\cdot\Delta_{\rho}^{(2)}\cdots\Delta_{\rho}^{(n)}$. Here  $\Delta_{\rho}^{(i)}=\id\otimes\ldots\id\otimes\Delta_{\rho}\otimes\id\otimes\ldots\otimes\id$, where $\Delta_{\rho}$ acts on the $i$-th register. Thus by induction it suffices to show $\norm{\Delta_{\rho}^{(i)}(P)}\leq\norm{P}$ for $i\in[n]$. Without loss of generality, we may assume that $i=1$. From~\cref{def:bonamibeckner}, it is easy to see $\Delta_{\rho}^{(1)}(P)=\rho P+\frac{1-\rho}{m}\id_m\otimes\br{\Tr_1 P}$. Thus
\begin{align*}
\norm{\Delta_{\rho}^{(1)}(P)}&\leq\rho\norm{P}+\frac{1-\rho}{m}\norm{\id_m\otimes\br{\Tr_1 P}}\\
&=\rho\norm{P}+\frac{1-\rho}{m}\norm{\Tr_1 P}\\
&=\rho\norm{P}+\frac{1-\rho}{m}\cdot m\norm{P}\\
\end{align*}
%let $\id_{(1)}$ be the identity map on the first quantum register, and $\id_{(-1)}$ be the identity map on the quantum registers except the first one. Then
%\norm{\Delta_{\rho}^{\otimes n}\br{P}}&=\norm{\br{\Delta_\rho\otimes\id_{(-1)}}\br{\id_{(1)}\otimes\Delta_{\rho}^{\otimes (n-1)}}\br{P}}\\
%&=\norm{\br{\Delta_\rho\otimes\id_{(-1)}}\br{\rho P+\frac{1-\rho}{m^{n-1}}\br{\Tr_{-1} P}\cdot\id_m}}

For item 3, it again suffices to show $\Delta_{\rho}^{(1)}(P)\geq0$ by induction. This is obvious since $\Delta_{\rho}^{(1)}(P)=\rho P+\frac{1-\rho}{m}\id_m\otimes\br{\Tr_1 P}$.
\end{proof}

Quantum maximal correlations introduced by Beigi~[9] are crucial to our analysis. They are a generalization of maximal correlation coefficients~[39, 30, 71] in classical information theory to the quantum setting.
\begin{definition}[Maximal correlation]~[9]\label{def:maximalcorrelation}
Given quantum systems $A, B$ and a bipartite state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, the maximal correlation of $\psi_{AB}$ is defined to be
\[\rho\br{\psi_{AB}}=\sup\set{\abs{\Tr\br{\br{P^{\dagger}\otimes Q}\psi_{AB}}}~:P\in\M\br{A}, Q\in\M\br{B},\atop\Tr~P=\Tr~Q=0, \nnorm{P}_2=\nnorm{Q}_2=1}.\]
\end{definition}

\begin{fact}~[9]\label{fac:maximalcorrlationone}
Given quantum systems $A, B$ and a bipartite quantum state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, it holds that $\rho\br{\psi_{AB}}\leq 1$.
%	\begin{enumerate}
%		\item $0\leq \rho\br{\psi_{AB}}\leq 1$.
%		\item $\rho\br{\psi_{AB}}=1$ if and only if there exist local measurements $\set{M_A,\id-M_A}$ and $\set{N_B,\id-N_B}$ such that $0<\Tr~\br{\psi_{AB}\br{M_A\otimes N_B}}<1$, and
%		\[\Tr~\br{\psi_{AB}\br{M_A\otimes\br{\id-N_B}}}=\Tr~\br{\psi_{AB}\br{\br{\id-M_A}\otimes N_B}}=0.\]
%	\end{enumerate}
\end{fact}

%The following proposition characterizes all the two-qubit states with maximal correlation being $1$.
%	Given a bipartite state $\psi_{AB}\in\D\br{\M_m\times\M_m}$, $\rho\br{\psi_{AB}}=1$ if and only if there exist local unitaries $U_A$ and $V_B$ such that
%	\begin{equation}\label{eqn:maximalcorrelation}
%	\br{U_A^{\dagger}\otimes V_B^{\dagger}}\psi_{AB}\br{U_A\otimes V_B}=\sum_{a,b=0}^1 c_{a,b}\ketbratwo{aa}{bb},
%	\end{equation}
%	where $\br{c_{ab}}_{a,b\in\set{0,1}}$ satisfies that $\begin{pmatrix}c_{00} & c_{01}\\ c_{10} & c_{11}\end{pmatrix}$ is a density operator.
%	Moreover, if $\psi_A=\psi_B=\frac{\id_2}{2}$, then $\rho\br{\psi_{AB}}=1$ if and only if there exist local unitaries $U_A$ and $V_B$ such that
%	\[\br{U_A^{\dagger}\otimes V_B^{\dagger}}\psi^{AB}\br{U_A\otimes V_B}=p\ketbra{\Phi}+\br{1-p}\ketbra{\Psi},\]
%	for $0\leq p\leq 1$, where $\ket{\Phi}=\frac{1}{\sqrt{2}}\br{\ket{00}+\ket{11}}$ and $\ket{\Psi}=\frac{1}{\sqrt{2}}\br{\ket{00}-\ket{11}}$.
%	Let $\set{M_A,\id-M_A}$ and $\set{N_B,\id-N_B}$ be the measurements induced by \cref{fac:maximalcorrlationone}. We may assume that
%	$M_A=a_0\ketbra{0}+a_1\ketbra{1}$ and $N_B=b_0\ketbra{0}+b_1\ketbra{1}$ up to local unitaries.
%	We claim that $M_A\neq\id_2$ and $N_B\neq\id_2$. Suppose $M_A=\id_2$. Then we have $0<\Tr~\psi_BN_B<1$ and $1-\Tr~\psi_BN_B=0$, contradicting to the fact that $\psi_B$ is a density operator. The argument for $N_B$ is similar. Thus we may further assume that $a_1\leq a_0\leq 1$ and $b_1\leq b_0\leq 1$ and $a_1, b_1<1, a_0,b_0>0$ Then $\Tr~\br{M_A\otimes\br{\id-M_B}}\psi_{AB}=0$ implies that $\bra{01}\psi_{AB}\ket{01}=0$. $\Tr~\br{\br{\id-M_A}\otimes M_B}=0$ implies that $\bra{10}\psi_{AB}\ket{10}=0$. We conclude Eq.~\cref{eqn:maximalcorrelation}.
%	The second part follows by elementary calculation.

\begin{definition}\label{def:noisyepr}
Given quantum systems $A$ and $B$ with $\dim\br{A}=\dim\br{B}=m$, a bipartite state $\psi_{AB}\in\D\br{A\otimes B}$ is an $m$-dimensional noisy maximally entangled state (MES) if $\psi_A=\psi_B=\frac{\id_m}{m}$ and its maximal correlation $\rho=\rho\br{\psi_{AB}}<1$.
\end{definition}

An interesting class of noisy MESs is the states obtained by depolarizing MESs with an arbitrarily small noise.
\begin{lemma}\label{lem:noisyeprmaximalcorrelation}
For any $0\leq\epsilon<1$ integer $m>1$, it holds that
\[\rho\br{\br{1-\epsilon}\ketbra{\Psi}+\epsilon\frac{\id_{m}}{m}\otimes \frac{\id_{m}}{m}}=1-\epsilon,\]
where $\ket{\Psi}=\frac{1}{\sqrt{m}}\sum_{i=0}^{m-1}|m,m\rangle$ is an $m$-dimensional MES.
\end{lemma}
\begin{proof}
The case that $m=2$ is proved by Beigi in~[9]. His proof can be directly generalized to any $m$. Here we provide a proof for completeness. Let $\Psi_{\epsilon}=\br{1-\epsilon}\ketbra{\Psi}+\epsilon\frac{\id_{m}}{m}\otimes\frac{\id_{m}}{m}$. From the definition of maximal correlations,
\begin{eqnarray*}
\rho\br{\Psi_{\epsilon}}=&\max\abs{\Tr\br{\br{X^{\dagger}\otimes Y}\Psi_{\epsilon}}}\\
&\mathrm{s.t. } \Tr X=\Tr Y=0\\
&\hspace{1.5 cm} \Tr X^{\dagger}X=\Tr Y^{\dagger}Y=m
\end{eqnarray*}
For $X$ and $Y$ satisfying the constraints above, we have
\begin{eqnarray*}
&&\abs{\Tr\br{\br{X^{\dagger}\otimes Y}\Psi_{\epsilon}}}\\
&=&\br{1-\epsilon}\abs{\bra{\Psi}\br{X^{\dagger}\otimes Y}\ket{\Psi}}\\
&=&\frac{1-\epsilon}{m}\abs{\Tr X^TY^{\dagger}}\\
\end{eqnarray*}
where the inequality is achieved by \[X=Y=\sum_{j=0}^{m-1}e^{2\pi\mathrm{i}\cdot j/ m}\ketbra{j}.\]
\end{proof}

The following proposition provides a useful characterization of quantum maximal correlations.
\begin{proposition}\label{prop:maximalvariance}
Given quantum systems $A,B$ and a bipartite state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, for any $Q\in\M\br{B}$,
\begin{equation}\label{eqn:TQ}
\max\set{\abs{\Tr\br{\br{P^{\dagger}\otimes Q}\psi_{AB}}}: P\in\M\br{A}, \nnorm{P}_2=1}
\end{equation}
is achieved by
\[P^*=\frac{\T\br{Q}}{\nnorm{\T\br{Q}}_2},\]
with the maximum value $\nnorm{\T\br{Q}}_2$, where $\T:\M\br{B}\rightarrow\M\br{A}$ is a Markov super-operator in \cref{def:markovoperator}.
\begin{equation}\label{eqn:Tmaxcorre}
\rho\br{\psi_{AB}}=\max\set{\nnorm{\T\br{Q}}_2: Q\in\M\br{B}, \Tr~Q=0,\nnorm{Q}_2=1}.
\end{equation}

Moreover, the maximal correlation in \cref{def:maximalcorrelation} can be achieved by a pair of Hermitian operators $\br{P,Q}$.
\end{proposition}

\begin{proof}
The proof complies with the one for Lemma 2.8 in~[61]. Let $P\in\M\br{A}$ achieves the maximum value in Eq.~\cref{eqn:TQ}. Then it satisfies that $\nnorm{P}_2=1$. Write $P=\alpha P^*+\beta P'$, where $\abs{\alpha}^2+\abs{\beta}^2=1$, $\nnorm{P'}_2=1$ and $\innerproduct{P^*}{P'}=0$. By the definition of Markov super-operators
\[0=\innerproduct{P'}{\T\br{Q}}=\Tr\br{\br{\br{P'}^{\dagger}\otimes Q}\psi_{AB}}.\]
So we should set $\abs{\alpha}=1.$ Moreover,
\[\Tr\br{\br{\T\br{Q}^{\dagger}\otimes Q}\psi_{AB}}=\nnorm{\T\br{Q}}^2_2.\]

Note that if $\Tr~Q=0$, then by the definition of Markov super-operators,
$$\Tr~\T\br{Q}=m_A\innerproduct{\id}{\T\br{Q}}=m_A\Tr\br{\br{\id\otimes Q}\psi_{AB}}=\frac{m_A}{m_B}\Tr~Q=0$$
where the third equality follows from \cref{fac:cauchyschwartz}.

By~\cref{lem:markovoperator}, $\T\br{Q}$ is Hermitian if $Q$ is Hermitian. Thus, to prove that the maximal correlation in \cref{def:maximalcorrelation} can be achieved by a pair of Hermitian operators $\br{P,Q}$, it suffices to prove that the maximum in Eq.~\cref{eqn:Tmaxcorre} can be achieved by a Hermitian matrix $Q$. Suppose $Q=Q_1+\mathrm{i}\cdot Q_2$ achieves the maximum value in Eq.~\cref{eqn:TQ} with Hermitian matrices $Q_1\neq 0$ and $Q_2\neq 0$. Then \[\Tr~Q=\Tr~Q_1+\mathrm{i}\cdot \Tr~Q_2=0\]
implies that  $\Tr~Q_1=\Tr~Q_2=0$ and
\[1=\nnorm{Q}_2^2=\nnorm{Q_1}_2^2+\nnorm{Q_2}_2^2\]
By~\cref{lem:markovoperator}, both $\T\br{Q_1}$ and $\T\br{Q_2}$ are Hermitian. By the linearity of Markov super-operators, we have
\begin{align*}
\nnorm{\T\br{Q}}_2&=\br{\frac{\nnorm{\T\br{Q_1}}_2^2+\nnorm{\T\br{Q_2}}_2^2}{\nnorm{Q_1}_2^2+\nnorm{Q_2}_2^2}}^{\frac{1}{2}}\\&\leq\max\set{\nnorm{\T\br{\frac{Q_1}{\nnorm{Q_1}_2}}}_2,\nnorm{\T\br{\frac{Q_2}{\nnorm{Q_2}_2}}}_2}.
\end{align*}
Thus at least one of $\frac{Q_1}{\nnorm{Q_1}_2}$ and $\frac{Q_2}{\nnorm{Q_2}_2}$ also achieves the maximum in Eq.~\cref{eqn:TQ}

\end{proof}

\begin{lemma}\label{lem:efronsteinortho}
Given quantum systems $A, B$ with $\dim A=m_A$ and $\dim B= m_B$, a bipartite quantum state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, let $\set{\A_{\sigma}}_{\sigma\in[m_A^2]_{\geq 0}}$ and $\set{\B_{\sigma}}_{\sigma\in[m_B^2]_{\geq 0}}$ be standard orthonormal bases in $\M\br{A}$ and $\M\br{B}$, respectively. It holds that
\[\Tr\br{\br{\A_{\sigma}\otimes\B_{\tau}}\psi_{AB}^{\otimes n}}=0,\]
whenever $\supp{\sigma}\neq\supp{\tau}$. Thus
\[\Tr\br{\br{A[S]\otimes B[T]}\psi_{AB}^{\otimes n}}=0,\]
whenever $S\neq T$, where $A[S]$ and $B[T]$ are obtained from the Efron-Stein decompositions of $A$ and $B$ in Definition~\ref{def:efronstein}.
\end{lemma}
\begin{proof}
For any $\sigma\in[m_A^2]_{\geq 0}, \tau\in[m_B^2]_{\geq 0}$ and  $\sigma\neq 0$ and $\tau\neq0$, it holds that
\[\Tr\br{\br{\A_{\sigma}\otimes\B_0}\psi_{AB}}=\frac{1}{m_A}\Tr~\A_{\sigma}=\innerproduct{\A_0}{\A_{\sigma}}=0.\]
Thus, for any $\sigma\in[m_A^2]_{\geq 0}^n$ and $\tau\in[m_B^2]_{\geq 0}^n$ with $\supp{\sigma}\neq\supp{\tau}$, it holds that
\[\Tr\br{\br{\A_{\sigma}\otimes\B_{\tau}}\psi_{AB}^{\otimes n}}=\prod_{i=1}^n\Tr\br{\br{\A_{\sigma_i}\otimes\B_{\tau_i}}\psi_{AB}}=0.\]
\end{proof}

\begin{proposition}\label{prop:markovenfronstein}
Given integers $n, m_A, m_B>0$, quantum systems $A$ and $B$, a bipartite quantum state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, $Q\in\M\br{B^n}$ and $S\subseteq[n]$, it holds that
\[\T\br{Q[S]}=\T\br{Q}[S],\]
where $\T:\M\br{B^n}\rightarrow\M\br{A^n}$ is a Markov super-operator with respect to $\psi_{AB}^{\otimes n}$ defined in \cref{def:markovoperator}.
\end{proposition}
\begin{proof} It suffices to show that
\[\innerproduct{X}{\T\br{Q[S]}}=\innerproduct{X}{\T\br{Q}[S]},\] for any $X\in\M\br{A^n}$.
By the definition,
\[\text{LHS}=\Tr\br{\br{X^{\dagger}\otimes Q[S]}\psi_{AB}^{\otimes n}}.\]
By \cref{def:efronstein} and \cref{prop:enfronsteinortho}, we have
\[\text{RHS}=\innerproduct{X[S]}{\T\br{Q}}=\Tr\br{\br{X[S]^{\dagger}\otimes Q}\psi_{AB}^{\otimes n}}.\]
By \cref{lem:efronsteinortho} and the Efron-Stein decompositions of $X$ and $Q$ defined in \cref{def:efronstein},
\[\Tr\br{\br{X[S]^{\dagger}\otimes Q}\psi_{AB}^{\otimes n}}=\Tr\br{\br{X^{\dagger}\otimes Q[S]}\psi_{AB}^{\otimes n}}=\Tr\br{\br{X[S]^{\dagger}\otimes Q[S]}\psi_{AB}^{\otimes n}}.\]
\end{proof}

\begin{proposition}\label{prop:markovoperatornorm}
Given integers $n, m_A, m_B>0$, quantum systems $A, B$, a bipartite quantum state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$, $Q\in\M\br{B^n}$ and $S\subseteq[n]$, it holds that
\[\nnorm{\T\br{Q[S]}}_2\leq\rho^{|S|}\nnorm{Q[S]}_2,\]
where $\rho=\rho\br{\psi_{AB}}$.
\end{proposition}
\begin{proof}
We may assume that $Q=Q[S]$ without loss of generality. It suffices to show the case that $S=[n]$. Let $\set{\A_i}_{i\in[m_A^2]_{\geq 0}}$ and $\set{\B_i}_{i\in[m_B^2]_{\geq 0}}$ be standard orthonormal bases in $\M\br{A}$ and $\M\br{B}$, respectively. We use a hybrid argument over $n$ registers. For $r\in[n]$, set $\T^{\br{r}}= \id_{\M\br{A}}^{\otimes\br{r-1}}\otimes\T\otimes\id_{\M\br{B}}^{\otimes\br{n-r}}$, $Q^{(0)}= Q$ and $Q^{\br{r}}=\T^{(r)}\br{Q^{(r-1)}}$, where $\id_{\M\br{A}}$ and $\id_{\M\br{B}}$ are the identity maps mapping $\M\br{A}$ to $\M\br{A}$ and $\M\br{B}$ to $\M\br{B}$, respectively. By \cref{lem:markovtensor}, we have $Q^{(n)}=\T\br{Q}$. By induction it suffices to show that
\begin{equation}\label{eqn:markovnormeq1}
\nnorm{Q^{(r)}}_2^2\leq\rho^2 \nnorm{Q^{(r-1)}}_2^2,
\end{equation}
\begin{equation}\label{eqn:markovnormeq2}
\end{equation}
where $Q^{(r)}[[n]]$ is defined by expanding $Q^{(r)}$ over \[\set{\A_{\sigma_{\leq r}}\otimes\B_{\sigma_{> r}}}_{\sigma\in[m_A^2]_{\geq 0}^r\times[m_B^2]_{\geq 0}^{n-r}},\]
because $\T=\T^{(n)}\circ\cdots\circ\T^{\br{1}}$.
Let $\set{\ket{u_i}}_{i\in[m_A]}$ and $\set{\ket{v_i}}_{i\in[m_B]}$ be orthonormal bases of $\complex^{m_A}$ and $\complex^{m_B}$, respectively. For any $s\in[m_A]^{r-1}\times[m_B]^{n-r}$, we define
\[\ket{w_s}=\ket{u_{s_1}}\otimes\ldots\otimes\ket{u_{s_{r-1}}}\otimes\ket{v_{s_{r+1}}}\otimes\ldots\otimes\ket{v_{s_n}}.\]
For any $s, t\in[m_A]^{r-1}\times[m_B]^{n-r}$, we define
\[P^{(r)}_{s,t}=\br{\bra{w_s}\otimes\id}Q^{(r)}\br{\ket{w_t}\otimes\id} ~\mbox{and}~ Q^{(r-1)}_{s,t}=\br{\bra{w_s}\otimes\id}Q^{(r-1)}\br{\ket{w_t}\otimes\id},\]
where $\ket{w_s}$ and $\ket{w_t}$ lie in the registers $\set{1,\ldots, r-1,r+1,\ldots, n}$. Note that $\T^{\br{r}}$ applies $\T$ to the $r$-th register and leaves other registers unchanged.  Then  $Q^{\br{r}}=\T^{\br{r}}\br{Q^{\br{r-1}}}$ implies that
\begin{equation}\label{eqn:tpq}
\end{equation}
And we also have
\begin{eqnarray*}
\end{eqnarray*}
by the induction $Q^{(r-1)}=Q^{(r-1)}[n]$.
By \cref{prop:maximalvariance},  $\nnorm{P^{(r)}_{s,t}}_2\leq\rho\nnorm{Q^{(r-1)}_{s,t}}_2$.
\begin{eqnarray*}
&=&\sum_{s,t}\Tr~\br{\bra{w_t}\otimes \id}\br{Q^{(r)}}^{\dagger}\br{\ket{w_s}\otimes\id}\br{\bra{w_s}\otimes\id}Q^{\br{r}}\br{\ket{w_t}\otimes\id}\\
&=&\sum_{t}\Tr~\br{\bra{w_t}\otimes \id}\br{Q^{(r)}}^{\dagger}Q^{\br{r}}\br{\ket{w_t}\otimes\id}\hspace{4mm}(\mbox{because $\sum_s\ketbra{w_s}=\id$})\\
\end{eqnarray*}
\[\sum_{s,t}\norm{Q^{(r-1)}_{s,t}}_2^2=\Tr~\br{Q^{(r-1)}}^{\dagger}Q^{(r-1)}.\]
Combining with Eq.~\cref{eqn:tpq} and \cref{prop:maximalvariance}, we conclude Eq.~\cref{eqn:markovnormeq1}.

For Eq.~\cref{eqn:markovnormeq2}, compute
\begin{eqnarray*}
&&\widehat{Q^{(r)}}\br{\sigma}=\widehat{\T^{\br{r}}\br{Q^{(r-1)}}}\br{\sigma}=\innerproduct{\A_{\sigma_{\leq r}}\otimes\B_{\sigma_{>r}}}{\T^{\br{r}}\br{Q^{(r-1)}}}\\
&=&\sum_{\tau:\abs{\tau}=n}\widehat{Q^{(r-1)}}\br{\tau}\innerproduct{\A_{\sigma_{\leq r}}\otimes\B_{\sigma_{>r}}}{\T^{\br{r}}\br{\A_{\tau_{<r}}\otimes\B_{\tau_{\geq r}}}}\\
\end{eqnarray*}
Note that
\[\innerproduct{\A_0}{\T\br{\B_{\tau_r}}}=\Tr\br{\br{\id\otimes\B_{\tau_r}}\psi_{AB}}=0,\]
as $\abs{\tau}=n$. Therefore, $\widehat{\T^{\br{r}}\br{Q}}\br{\sigma}=0$ if $\abs{\sigma}<n$. We conclude Eq.~\cref{eqn:markovnormeq2}.
\end{proof}
A useful property of (classical) maximal correlation coefficients is {\em tensorization}, which states that the maximal correlation of multiple independent identical copies of a distribution is the same as the one of one copy. The same property also holds for the quantum maximal correlation shown by Beigi~[9]. Here we provide a different proof.
\begin{fact}~[9]\label{prop:maximalcorrelationtensorisation}Given quantum systems $A, B$ with $\dim A=m_A$ and $\dim B= m_B$, a bipartite quantum state $\psi_{AB}$ with $\psi_A=\frac{\id_{m_A}}{m_A}$ and $\psi_B=\frac{\id_{m_B}}{m_B}$,  it holds that
\[\rho\br{\psi_{AB}^{\otimes n}}=\rho\br{\psi_{AB}}.\]
\end{fact}
\begin{proof}
Given $Q\in\M\br{\B^n}$ with $\Tr~Q=0$ and $\nnorm{Q}_2=1$, we use the Efron-Stein decomposition $Q=\sum_{S\neq\emptyset}Q[S]$ to obtain
\begin{eqnarray*}
&=&\nnorm{\sum_{S\neq\emptyset}\T\br{Q[S]}}_2^2\quad\quad\mbox{(linearity of $\T$)}\\
&=&\sum_{S\neq\emptyset}\nnorm{\T\br{Q}[S]}_2^2\quad\quad\mbox{(orthogonality of the Efron-Stein decomposition)}\\
&=&\rho^2\nnorm{Q}_2^2\quad\quad\mbox{(orthogonality of the Efron-Stein decomposition)}\\
\end{eqnarray*}
From \cref{prop:maximalvariance}, $\rho\br{\psi^{\otimes n}_{AB}}\leq\rho\br{\psi_{AB}}$. The other direction trivially follows by definition.
\end{proof}

\section{Main results}\label{sec:mainresult}
\begin{theorem}\label{thm:nijs}
Let $\epsilon\in(0,1)$, integers $n,m,a,b,t>0$, $\psi_{AB}$ be a noisy MES. Namely, $\psi_A=\psi_B=\frac{\id_m}{m}$. Let $\rho=\rho\br{\psi_{AB}}<1$ be the maximal correlation of $\psi_{AB}$ defined in \cref{def:maximalcorrelation}. Then there exists an explicitly computable $D=D\br{\rho,\epsilon,a,b,m,t}$, such that for any sequences of POVMs $$\vec{P_1},\ldots,\vec{P_a}~\mbox{and}~\vec{Q_1},\ldots,\vec{Q_b},$$ where

$$\vec{P_u}=\br{P_{u,1},\ldots, P_{u,t}}~\mbox{and}~\vec{Q_v}=\br{Q_{v,1},\ldots, Q_{v,t}}$$ and $P_{u,i},Q_{v,j}\in\H_m^{\otimes n}$ for $u\in[a],v\in[b],i,j\in[t]$,  there exist sequences of positive semidefinite operators $$\vec{\widetilde{P}_1},\ldots,\vec{\widetilde{P}_a}~\mbox{and}~\vec{\widetilde{Q}_1},\ldots,\vec{\widetilde{Q}_b},$$ where
$$\vec{\widetilde{P}_u}=\br{\widetilde{P}_{u,1}\ldots,\widetilde{P}_{u,t}}~\mbox{and}~\vec{\widetilde{Q}_v}=\br{\widetilde{Q}_{v,1},\ldots,\widetilde{Q}_{v,t}}$$ for $\widetilde{P}_{u,i},\widetilde{Q}_{v,j}\in\H_m^{\otimes D}$, $u\in[a],v\in[b],i,j\in[t]$, such that the following holds.

\begin{enumerate}
\item For $u\in[a],v\in[b]$, $\vec{\widetilde{P}_u}, \vec{\widetilde{Q}_v}$ are sub-POVMs. Namely,
$$\sum_{j=1}^t\widetilde{P}_{u,j}\leq\id, \sum_{j=1}^t\widetilde{Q}_{v,j}\leq\id~\mbox{and}~\widetilde{P}_{u,j}\geq0, \widetilde{Q}_{v,j}\geq0~\mbox{for}~j\in[t].$$
\item For any $u\in[a],v\in[b],i,j\in[t]$, $$\abs{\Tr\br{\br{P_{u,i}\otimes Q_{v,j}}\psi_{AB}^{\otimes n}}-\Tr\br{\br{\widetilde{P}_{u,i}\otimes \widetilde{Q}_{v,j}}\psi_{AB}^{\otimes D}}}\leq\epsilon.$$

%			\item If $\vec{P_u}=\vec{P_v}$, then $\vec{\widetilde{P}_{u}}=\vec{\widetilde{P}_{v}}$. If $\vec{Q_u}=\vec{Q_v}$, then $\vec{\widetilde{Q}_u}=\vec{\widetilde{Q}_v}$.
\end{enumerate}
In particular, one may choose $$D=\exp\br{\mathrm{poly}\br{a,b,t,\exp\br{\mathrm{poly}\br{\frac{1}{\epsilon},\frac{1}{1-\rho},\log m}}}}.$$
\end{theorem}
\begin{remark}
Here we assume for simplicity that the sizes of the output sets of the measurements on both sides are same. However, the same argument also holds when they are different by setting $t$ to be the larger one.
\end{remark}
The proof is deferred to the end of this section. The following is an application of \cref{thm:nijs} to the decidability of nonlocal games.

\begin{theorem}\label{thm:decidable}
Given parameters $0<\epsilon,\rho<1$, an integer $m\geq 2$, a noisy MES state $\psi_{AB}$, i.e.,  $\psi_A=\psi_B=\frac{\id_m}{m}$ with the maximal correlation $\rho=\rho\br{\psi_{AB}}<1$
as defined in \cref{def:maximalcorrelation}, let $G$  be a nonlocal game with the question sets $\X,\Y$ and the answer sets $\A,\B$. Suppose the players share arbitrarily many copies of $\psi_{AB}$. Let $\omega^*(G,\psi_{AB})$ be the supremum of the winning probability that the players can achieve. Then there exists an explicitly computable bound $D=D\br{\abs{\X},\abs{\Y},\abs{\A},\abs{\B},m,\epsilon,\rho}$ such that it suffices for the players to share $D$ copies of $\psi_{AB}$ to achieve the winning probability at least $\omega^*(G,\psi_{AB})-\epsilon$. In particular, one may choose
$$D=\exp\br{\mathrm{poly}\br{\abs{\X},\abs{\Y}, \exp\br{\mathrm{poly}\br{\abs{\A},\abs{\B},\frac{1}{\epsilon},\frac{1}{1-\rho}},\log m}}}.$$
\end{theorem}
\begin{proof}
We assume that $\abs{\A}=\abs{B}=t$ without loss of generality. Suppose the players share $n$ copies of $\psi_{AB}$ and employ the strategies $$\br{\set{\vec{P_x}=\br{P_{x,1},\ldots, P_{x,t}}}_{x\in\X},\set{\vec{Q_y}=\br{Q_{y,1},\ldots, Q_{y,t}}}_{y\in\Y}}$$ with the winning probability $\omega$. For simplicity, we set $\X=\set{1,2,\ldots,\abs{\X}}$ and $\Y=\set{1,2,\ldots,\abs{\Y}}$.

We apply \cref{thm:nijs} to the following two sequences of POVMs
$$\br{\vec{P_1},\vec{P_2},\ldots\vec{P_{\abs{\X}}}}~\mbox{and}~\br{\vec{Q_1},\vec{Q_2},\ldots, \vec{Q_{\abs{\Y}}}}$$
with parameters $\epsilon\leftarrow\epsilon/t^2, t\leftarrow t$. Let $\vec{\widetilde{P}_1},\ldots,\vec{\widetilde{P}_{|\X|}},\vec{\widetilde{Q}_1},\ldots,\vec{\widetilde{Q}_{|Y|}}$ be the sequences sub-POVMs induced by \cref{thm:nijs}.
%which are well-defined thanks to item 3 in \cref{thm:nijs}.
We claim that the strategy $$\br{\set{\vec{\widetilde{P_{x}}}}_{x\in\X},\set{\vec{\widetilde{Q_{y}}}}_{y\in\Y}}$$ wins the game with probability $\widetilde{\omega}\geq \omega-\epsilon$. Moreover, they can be easily converted to valid POVMs without lowering the winning probability.

$$\vec{\widetilde{P}_x}=\set{\widetilde{P}_{x,1},\ldots,\widetilde{P}_{x,t}}, \vec{\widetilde{Q}_y}=\set{\widetilde{Q}_{y,1},\ldots,\widetilde{Q}_{y,t}}$$ and $$\nu_{xy}\br{a,b}=\Tr\br{\br{P_{x,a}\otimes Q_{y,b}}\psi_{AB}^{\otimes n}}$$
and $$\widetilde{\nu}_{xy}\br{a,b}=\Tr\br{\br{\widetilde{P}_{x,a}\otimes \widetilde{Q}_{y,b}}\psi_{AB}^{\otimes D}}.$$
From \cref{thm:nijs}, for any $(x,y,a,b)\in\X\times\Y\times[t]\times[t]$,
\begin{eqnarray*}
% \nonumber % Remove numbering (before each equation)
\abs{\nu_{xy}\br{a,b}-\widetilde{\nu}_{xy}\br{a,b}}\leq\epsilon/t^2
\end{eqnarray*}
\begin{eqnarray*}
% \nonumber % Remove numbering (before each equation)
&&\abs{\omega-\tilde{\omega}}=\abs{\sum_{xy}\mu\br{x,y}\br{\nu_{xy}\br{a,b}-\widetilde{\nu}_{xy}\br{a,b}}V(x,y,a,b)} \\&\leq&\sum_{xy}\mu\br{x,y}\sum_{a,b}\abs{\nu_{xy}\br{a,b}-\widetilde{\nu}_{xy}\br{a,b}}\\
\end{eqnarray*}

\end{proof}

\begin{remark}
\cref{thm:nijs} and \cref{thm:decidable} can be directly generalized to the case when $\psi_A=\frac{\id_{m_A}}{m_A}$, $\psi_B=\frac{\id_{m_B}}{m_B}$ and $m_A\neq m_B$.
\end{remark}

To prove \cref{thm:nijs}, we need the following intermediate lemma for technical reasons.

\begin{lemma}\label{lem:nijslem}
With the same setting of \cref{thm:nijs}, the following holds.
\begin{enumerate}
\item For $1\leq u\leq s$, $\vec{\widetilde{P}_u}, \vec{\widetilde{Q}_u}$ are sub-POVMs. Namely,
$$\sum_{j=1}^t\widetilde{P}_{u,j}\leq\id, \sum_{j=1}^t\widetilde{Q}_{u,j}\leq\id~\mbox{and}~\widetilde{P}_{u,j}\geq0, \widetilde{Q}_{u,j}\geq0 ~\mbox{for}~ j\in[t].$$
\item For any $u\in[s],i,j\in[t]$, $$\abs{\Tr\br{\br{P_{u,i}\otimes Q_{u,j}}\psi_{AB}^{\otimes n}}-\Tr\br{\br{\widetilde{P}_{u,i}\otimes \widetilde{Q}_{u,j}}\psi_{AB}^{\otimes D}}}\leq\epsilon.$$

\item If $\vec{P_u}=\vec{P_v}$, then $\vec{\widetilde{P}_{u}}=\vec{\widetilde{P}_{v}}$. If $\vec{Q_u}=\vec{Q_v}$, then $\vec{\widetilde{Q}_u}=\vec{\widetilde{Q}_v}$.
\end{enumerate}

\end{lemma}
\begin{proof}[Proof of \cref{thm:nijs}]
Applying Lemma~\ref{lem:nijslem} to the following two sequences of POVMs
$$\br{\underbrace{\vec{P_1},\ldots, \vec{P_1}}_{b~\text{times}},\underbrace{\vec{P_2},\ldots, \vec{P_2}}_{b~\text{times}},\ldots, \underbrace{\vec{P_a},\ldots, \vec{P_a}}_{b~\text{times}}}$$
$$\br{\vec{Q_1},\ldots, \vec{Q_b},\vec{Q_1},\ldots, \vec{Q_b},\ldots,\vec{Q_1},\ldots, \vec{Q_b}}$$
with parameters $n\leftarrow n,\rho\leftarrow \rho,\epsilon\leftarrow \epsilon,a\leftarrow ab,b\leftarrow ab,t\leftarrow t$, we obtain
$$\br{\underbrace{\vec{\widetilde{P_1}},\ldots, \vec{\widetilde{P_1}}}_{b~\text{times}},\underbrace{\vec{\widetilde{P_2}},\ldots, \vec{\widetilde{P_2}}}_{b~\text{times}},\ldots, \underbrace{\vec{\widetilde{P_a}},\ldots, \widetilde{\vec{P_a}}}_{b~\text{times}}}$$
$$\br{\vec{\widetilde{Q_1}},\ldots, \vec{\widetilde{Q_b}},\vec{\widetilde{Q_1}},\ldots, \vec{\widetilde{Q_b}},\ldots,\vec{\widetilde{Q_1}},\ldots, \vec{\widetilde{Q_b}}}$$
guaranteed by Item 3 of \cref{lem:nijslem}. Item 1 and Item 2 in \cref{thm:nijs} follow by Item 1 and Item 2 in \cref{lem:nijslem}.
\end{proof}
It remains to show \cref{lem:nijslem}.

\begin{proof}[Proof of \cref{lem:nijslem}]
Let $\delta,\tau $ be parameters which are chosen later. The proof is composed of several steps.
\begin{itemize}
\item \textbf{Smooth operators}. For $u\in[s],i\in[t]$, we apply the map $f$ implied by \cref{lem:smoothing of strategies} to $\set{P_{u,i}}_{u\in[s],i\in[t]}$ and $\set{Q_{u,i}}_{u\in[s],i\in[t]}$ to get $\set{P_{u,i}^{(1)}}_{u\in[s],i\in[t]}$ and $\set{Q_{u,i}^{(1)}}_{u\in[s],i\in[t]}$, respectively, and $ d_1=\frac{2\log^2(1/\delta)}{C\br{1-\rho}\delta}$ for some constant $C$ satisfying the following.
\bigskip
\begin{enumerate}
\item $\set{P_{u,i}^{(1)}}_{1\leq i\leq t}$ and $\set{Q_{u,i}^{(1)}}_{1\leq i\leq t}$ are POVMs for $1\leq u\leq s$, which is implied by item 5 in \cref{lem:smoothing of strategies}.
\item For any $i\in[t],u\in[s]$,$$\nnorm{P_{u,i}^{(1)}}_2\leq\nnorm{P_{u,i}}_2~\mbox{and}~\nnorm{Q_{u,i}^{(1)}}_2\leq\nnorm{Q_{u,i}}_2.$$
\item For any $i,j\in[t],u\in[s]$,
$$\abs{\Tr\br{\br{P_{u,i}^{(1)}\otimes\ Q^{(1)}_{u,j}}\psi^{\otimes n}_{AB}}-\Tr\br{\br{P_{u,i}\otimes Q_{u,j}}\psi^{\otimes n}_{AB}}}\leq\delta.$$
\item For any $i\in[t],u\in[s]$,$$\nnorm{\br{P_{u,i}^{(1)}}^{>d_1}}^2_2\leq\delta~\mbox{and}~\nnorm{\br{Q_{u,i}^{(1)}}^{>d_1}}^2_2\leq\delta.$$
\item If $P_{u,i}=P_{v,i}$, then $P_{u,i}^{(1)}=P_{v,i}^{(1)}$. If $Q_{u,i}=Q_{v,i}$, then $Q_{u,i}^{(1)}=Q_{v,i}^{(1)}$.
\end{enumerate}
\bigskip

%\item\textbf{Regularization}. For any $u\in[s]$, applying \cref{lem:regular} to $P_{u,i}^{(1)}$ and $Q_{u,i}^{(1)}$ with $\delta\leftarrow\delta, \epsilon\leftarrow\tau, d\leftarrow d_1$, we obtain a set $H_u\subseteq[n]$ of size $\abs{H_u}\leq\frac{2td_1}{\tau}$ such that for all $i\in[t]$
%			\[\br{\forall j\notin H_u}~\influence_j\br{\br{P_{u,i}^{(1)}}^{\leq d_1}}\leq\tau,~\mbox{and}~\influence_j\br{\br{Q_{u,i}^{(1)}}^{\leq d_1}}\leq\tau.\]
%			Set $H=\bigcup_{u\in[s]}H_{x,y,u}$. Then $h=\abs{H}\leq\frac{2std_1}{\tau}$. It holds that for any $u\in[s]$
%			\begin{enumerate}
%				\item $\br{\forall i\in[t],j\notin H}~\influence_j\br{\br{P_{u,i}^{(1)}}^{\leq d_1}}\leq\tau,~\mbox{and}~\influence_j\br{\br{Q_{u,i}^{(1)}}^{\leq d_1}}\leq\tau;$
%				\item $\br{\forall i,j\in[t]}\Tr~\br{P_{u,i}^{(1)}\otimes Q_{u,j}^{(1)}}\psi_{AB}^{\otimes h}=\sum_{\sigma\in[m^2]_{\geq 0}^h}c_{\sigma}\Tr~\br{P_{u,i,\sigma}^{(1)}\otimes Q_{u,j,\sigma}^{(1)}}\psi_{AB}^{\otimes (n-h)},$
%				where
%				$\br{c_i}_{i=0}^{m^2-1}$ are the singular values of the matrix $\mathsf{Corr}\br{\psi_{AB}}$ defined in \cref{def:covariancematrix} and $c_{\sigma}=c_{\sigma_1}\cdot c_{\sigma_2}\cdots c_{\sigma_h}$ and
%				\[P_{u,i,\sigma}^{(1)}=\sum_{\tau\in[m^2]_{\geq 0}^n:\tau_H=\sigma}\widehat{P_{u,i}^{(1)}}\br{\sigma}\A_{\sigma}~\mbox{and}~Q_{u,j,\sigma}^{(1)}=\sum_{\tau\in[m^2]_{\geq 0}^n:\tau_H=\sigma}\widehat{Q_{u,j}^{(1)}}\br{\sigma}\B_{\sigma},\]
%			\end{enumerate}
%			for standard orthonormal basis $\set{\A_i}_{i=0}^{m^2-1}$ and $\set{\B_i}_{i=0}^{m^2-1}$.
\item\textbf{Regularization}. For any $u\in[s]$ applying \cref{lem:regular} to $P_{u,i}^{(1)}$ and $Q_{u,i}^{(1)}$ with $\delta\leftarrow\delta, \epsilon\leftarrow\tau, d\leftarrow d_1$, we obtain sets $H_{u,i}\subseteq[n]$ of size $\abs{H_{u,i}}\leq\frac{2d_1}{\tau}$ such that for all $i\in[t]$

\[\br{\forall r\notin H_{u,i}}~\influence_r\br{\br{P_{u,i}^{(1)}}^{\leq d_1}}\leq\tau,~\mbox{and}~\influence_r\br{\br{Q_{u,i}^{(1)}}^{\leq d_1}}\leq\tau.\]
Set $H=\bigcup_{u\in[s],i\in[t]}H_{u,i}$. Then $h=\abs{H}\leq\frac{2std_1}{\tau}$. Without loss of generality, assume $H=[h]$. It holds that for any $u\in[s]$

\begin{enumerate}
\item $\br{\forall i\in[t],r\notin H}~\influence_r\br{\br{P_{u,i}^{(1)}}^{\leq d_1}}\leq\tau,~\mbox{and}~\influence_r\br{\br{Q_{u,i}^{(1)}}^{\leq d_1}}\leq\tau;$
\item $\forall i,j\in[t]$, we have
$$\Tr\br{\br{P_{u,i}^{(1)}\otimes Q_{u,j}^{(1)}}}\psi_{AB}^{\otimes n}=\sum_{\sigma\in[m^2]_{\geq 0}^h}c_{\sigma}\Tr\br{\br{P_{u,i,\sigma}^{(1)}\otimes Q_{u,j,\sigma}^{(1)}}\psi_{AB}^{\otimes (n-h)}},$$

$\br{c_i}_{i=0}^{m^2-1}$ are the singular values of the matrix $\mathsf{Corr}\br{\psi_{AB}}$ in non-increasing order defined in \cref{def:covariancematrix}, $c_{\sigma}=c_{\sigma_1}\cdot c_{\sigma_2}\cdots c_{\sigma_h}$ and
\[P_{u,i,\sigma}^{(1)}=\sum_{\tau\in[m^2]_{\geq 0}^n:\tau_H=\sigma}\widehat{P_{u,i}^{(1)}}\br{\tau}\A_{\tau_{H^c}}\]
\[Q_{u,j,\sigma}^{(1)}=\sum_{\tau\in[m^2]_{\geq 0}^n:\tau_H=\sigma}\widehat{Q_{u,j}^{(1)}}\br{\tau}\B_{\tau_{H^c}},\]
\end{enumerate}
for some standard orthonormal bases $\set{\A_i}_{i=0}^{m^2-1}$ and $\set{\B_i}_{i=0}^{m^2-1}$.

\item \textbf{Invariance from $\H_m^{\otimes n}$ to $L^2\br{\H_m^{\otimes h},\gamma_{2(m^2-1)\br{n-h}}}$}. ~For any $u\in[s]$, applying \cref{lem:jointinvariance} to $P_{u,i}^{(1)}$'s and $Q_{u,i}^{(1)}$'s and $H$, we obtain joint random operators
\[\br{\mathbf{P}_{u,i}^{(2)},\mathbf{Q}_{u,j}^{(2)}}\in L^2\br{\M_m^{\otimes h},\gamma_{2(m^2-1)\br{n-h}}}\times  L^2\br{\M_m^{\otimes h},\gamma_{2(m^2-1)\br{n-h}}}\]
for $1\leq i,j\leq 2(m^2-1)(n-h)$ with same joint random variables\linebreak $\br{\mathbf{g}_i,\mathbf{h}_i}_{i=1}^{2(m^2-1)\br{n-h}}\sim \G_{\rho}^{\otimes 2(m^2-1)(n-h)}$ such that the followings hold.

\bigskip
\begin{enumerate}
\item 	$\mathbf{P}_{u,i}^{(2)}$ and $\mathbf{Q}_{u,i}^{(2)}$ are both multilinear and of degree at most $d_1$ for $u\in[s], i\in[t]$.
\item $\sum_{i=1}^t\mathbf{P}_{u,i}^{(2)}=\id$ and $\sum_{i=1}^t\mathbf{Q}_{u,i}^{(2)}=\id$ for $u\in[s]$.
\item For any $u\in[s],i\in[t]$ $$N_2\br{\mathbf{P}_{u,i}^{(2)}}\leq\nnorm{P_{u,i}^{(1)}}_2,N_2\br{\mathbf{Q}_{u,i}^{(2)}}\leq\nnorm{Q_{u,i}^{(1)}}_2$$
\item For any $u\in[s],i,j\in[t]$ $$\abs{\Tr\br{\br{P_{u,i}^{(1)}\otimes Q_{u,j}^{(1)}}\psi_{AB}^{\otimes n}}-\expec{}{\Tr~\br{\br{\mathbf{P}_{u,i}^{(2)}\otimes\mathbf{Q}_{u,j}^{(2)}}\psi_{AB}^{\otimes h}}}}\leq\delta$$
\item For any $u,v\in[s]$ $$\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(2)}}}\leq O\br{t\br{\br{3^{d_1}m^{d_1/2}\sqrt{\tau}d_1}^{2/3}+\sqrt{\delta}}}$$
$$\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(2)}}}\leq O\br{t\br{\br{3^{d_1}m^{d_1/2}\sqrt{\tau}d_1}^{2/3}+\sqrt{\delta}}}$$

\item If $P_{u,i}^{(1)}=P_{v,i}^{(1)}$, then $\mathbf{P}_{u,i}^{(2)}=\mathbf{P}_{v,i}^{(2)}$. If $Q_{u,i}^{(1)}=Q_{v,i}^{(1)}$, then $\mathbf{Q}_{u,i}^{(2)}=\mathbf{Q}_{v,i}^{(2)}$.
\end{enumerate}
\bigskip
\item\textbf{Dimension reduction}. ~For any $u\in[s],i,j\in[t]$, applying \cref{lem:dimensionreduction} to \linebreak$\br{\mathbf{P}_{u,i}^{(2)},\mathbf{Q}_{v,j}^{(2)}}$ with $\delta\leftarrow\delta/2st^2, d\leftarrow d_1, n\leftarrow 2(m^2-1)(n-h),\alpha\leftarrow 1/9st^2$, if we sample $\mathbf{M}\sim\gamma_{n\times n_0}$, then items 1 to 3 in ~\cref{lem:dimensionreduction} hold for $f_{\mathbf{M}}\br{\mathbf{P}_{u,i}^{(2)}}$, $f_{\mathbf{M}}\br{\mathbf{Q}_{u,i}^{(2)}}$ with probability at least $1-\delta/2st^2-2/9st^2$, where $f_{\mathbf{M}}$ is the function introduced in \cref{lem:dimensionreduction}. Further applying a union bound on $u\in[s],i,j\in[t]$, we obtain that items 1 to 3 in~\cref{lem:dimensionreduction} hold with probability at least $7/9-\delta/2>0$. Thus we have joint random operators $\br{\mathbf{P}_{u,i}^{(3)},\mathbf{Q}_{u,i}^{(3)}}\in L^2\br{\H_m^{\otimes h},\gamma_{n_0}}\times L^2\br{\H_m^{\otimes h},\gamma_{n_0}}$ with the joint random variables drawn from $\G_{\rho}^{\otimes n_0}$ such that the following holds for all $u\in[s]$.
\bigskip
\begin{enumerate}
\item $\sum_{i=1}^t\mathbf{P}_{u,i}^{(3)}=\id$ and $\sum_{i=1}^t\mathbf{Q}_{u,i}^{(3)}=\id$.
\item For all $i\in[t]$,  $$N_2\br{\mathbf{P}_{u,i}^{(3)}}\leq(1+\delta)N_2\br{\mathbf{P}_{u,i}^{(2)}}~\mbox{and}~N_2\br{\mathbf{Q}_{u,i}^{(3)}}\leq(1+\delta)N_2\br{\mathbf{Q}_{u,i}^{(2)}}.$$

\item $$\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(3)}}}\leq 3t\sqrt{s}\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(2)}}};$$
$$\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(3)}}}\leq 3t\sqrt{s}\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(2)}}}.$$
\item For all $i,j\in[t]$,
\begin{multline*}
\abs{\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(3)}\otimes \mathbf{Q}_{u,j}^{(3)}}\psi_{AB}^{\otimes h}}}-\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(2)}\otimes \mathbf{Q}_{u,j}^{(2)}}\psi_{AB}^{\otimes h}}}}\\
\leq\delta N_2\br{\mathbf{P}_{u,i}^{(2)}}N_2\br{\mathbf{Q}_{u,j}^{(2)}}.
\end{multline*}

\item If $\mathbf{P}_{u,i}^{(2)}=\mathbf{P}_{v,i}^{(2)}$, then $\mathbf{P}_{u,i}^{(3)}=\mathbf{P}_{v,i}^{(3)}$.
If $\mathbf{Q}_{u,i}^{(2)}=\mathbf{Q}_{v,i}^{(2)}$, then $\mathbf{Q}_{u,i}^{(3)}=\mathbf{Q}_{v,i}^{(3)}$.
\end{enumerate}
\bigskip
Here $n_0=\frac{m^{O(h)}d_1^{O\br{d_1}}s^6t^{12}}{\delta^6}$.
\item\textbf{Smooth random operators}. For any $u\in[s]$, we apply \cref{lem:smoothgaussian} to $\br{\mathbf{P}_{u,i}^{(3)},\mathbf{Q}_{u,i}^{(3)}}$ with $ h\leftarrow h, n\leftarrow n_0$ and obtain joint random operators $\br{\mathbf{P}_{u,i}^{(4)},\mathbf{Q}_{u,i}^{(4)}}\in L^2\br{\H_m^{\otimes h},\gamma_{n_0}}\times L^2\br{\H_m^{\otimes h},\gamma_{n_0}}$ such that the following holds.
\bigskip
\begin{enumerate}
\item $\sum_{i=1}^t\mathbf{P}_{u,i}^{(4)}=\id$ and $\sum_{i=1}^t\mathbf{Q}_{u,i}^{(4)}=\id$.
\item For all $i\in[t]$, $\deg\br{\mathbf{P}_{u,i}^{(4)}}\leq d_2$ and $\deg\br{\mathbf{Q}_{u,i}^{(4)}}\leq d_2$.

\item For all $i\in[t]$, $N_2\br{\mathbf{P}_{u,i}^{(4)}}\leq N_2\br{\mathbf{P}_{u,i}^{(3)}}$ and $N_2\br{\mathbf{Q}_{u,i}^{(4)}}\leq N_2\br{\mathbf{Q}_{u,i}^{(3)}}$.
\item
\begin{multline*}
\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(4)}}}\\
\leq2\br{\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(3)}}}+\delta \br{\sum_{i=1}^tN_2\br{\mathbf{P}_{u,i}^{(3)}}^2}};
\end{multline*}
\begin{multline*}\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(4)}}}\\
\leq2\br{\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(3)}}}+\delta \br{\sum_{i=1}^tN_2\br{\mathbf{Q}_{u,i}^{(3)}}^2}}.
\end{multline*}
\item For all $i,j\in[t]$,
\begin{multline*}
\abs{\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(4)}\otimes\mathbf{Q}_{u,j}^{(4)}}\psi_{AB}^{\otimes h}}}-\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(3)}\otimes\mathbf{Q}_{u,j}^{(3)}}\psi_{AB}^{\otimes h}}}}\\
\leq \delta N_2\br{\mathbf{P}_{u,i}^{(3)}}N_2\br{\mathbf{Q}_{u,j}^{(3)}}.
\end{multline*}

\item If $\mathbf{P}_{u,i}^{(3)}=\mathbf{P}_{v,i}^{(3)}$, then $\mathbf{P}_{u,i}^{(4)}=\mathbf{P}_{v,i}^{(4)}$.
If $\mathbf{Q}_{u,i}^{(3)}=\mathbf{Q}_{v,i}^{(3)}$, then $\mathbf{Q}_{u,i}^{(4)}=\mathbf{Q}_{v,i}^{(4)}$.
\end{enumerate}
\bigskip
Here $d_2=O\br{\frac{\log^2\frac{1}{\delta}}{\delta\br{1-\rho}}}$.

\item\textbf{Multilinearization}. For any $u\in[s]$, suppose
\[\br{\mathbf{P}_{u,i}^{(4)},\mathbf{Q}_{u,i}^{(4)}}=\br{\sum_{\sigma\in[m^2]_{\geq 0}^h}p^{(4)}_{u,i,\sigma}\br{\mathbf{g}}\A_{\sigma},\sum_{\sigma\in[m^2]_{\geq 0}^h}q^{(4)}_{u,i,\sigma}\br{\mathbf{h}}\B_{\sigma}},\]
where $\br{\mathbf{g},\mathbf{h}}\sim\G_{\rho}^{\otimes n_0}$.
Applying \cref{lem:multiliniearization} with $d\leftarrow d_2,h\leftarrow h, n\leftarrow n_0,\delta\leftarrow\tau$, we obtain the joint random operators
\[\br{\mathbf{P}_{u,i}^{(5)},\mathbf{Q}_{u,i}^{(5)}}=\br{\sum_{\sigma\in[m^2]_{\geq 0}^h}p^{(5)}_{u,i,\sigma}\br{\mathbf{x}}\A_{\sigma},\sum_{\sigma\in[m^2]_{\geq 0}^h}q^{(5)}_{u,i,\sigma}\br{\mathbf{y}}\B_{\sigma}}\]
where ${\br{\mathbf{x},\mathbf{y}}\sim\G_{\rho}^{\otimes n_0n_1}}$, with $n_1=O\br{\frac{d_2^2}{\tau^2}}$ such that the following holds.
\bigskip
\begin{enumerate}
\item $\mathbf{P}_{u,i}^{(5)}$ and $\mathbf{Q}_{u,i}^{(5)}$ are both multilinear for $1\leq i\leq t$.
\item $\sum_{i=1}^t\mathbf{P}_{u,i}^{(5)}=\id$ and $\sum_{i=1}^t\mathbf{Q}_{u,i}^{(5)}=\id$.
\item For all $i\in[t]$, both $\deg\br{\mathbf{P}_{u,i}^{(5)}}$ and $\deg\br{\mathbf{Q}_{u,i}^{(5)}}$ are at most $d_2$.
\item For all $\br{i,j,k}\in[t]\times[n_0]\times[n_1]$ and $\sigma\in[m^2]_{\geq 0}^h$,

\item For all $i\in[t]$, $N_2\br{\mathbf{P}_{u,i}^{(5)}}\leq N_2\br{\mathbf{P}_{u,i}^{(4)}}~\mbox{and}~N_2\br{\mathbf{Q}_{u,i}^{(5)}}\leq N_2\br{\mathbf{Q}_{u,i}^{(4)}}.$
\item \begin{multline*}\abs{\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(5)}}}-\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{P}_{u,i}^{(4)}}}}\\\leq 4\tau \br{\sum_{i=1}^tN_2\br{\mathbf{P}_{u,i}^{(4)}}^2};\end{multline*}

\begin{multline*}\abs{\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(5)}}}-\expec{}{\frac{1}{m^h}\sum_{i=1}^t\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(4)}}}}\\\leq 4\tau \br{\sum_{i=1}^tN_2\br{\mathbf{Q}_{u,i}^{(4)}}^2}.\end{multline*}
\item For all $i,j\in[t]$, \begin{multline*}\abs{\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(5)}\otimes\mathbf{Q}_{u,j}^{(5)}}\psi_{AB}^{\otimes h}}}-\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(4)}\otimes\mathbf{Q}_{u,j}^{(4)}}\psi_{AB}^{\otimes h}}}}\\\leq\delta N_2\br{\mathbf{P}_{u,i}^{(4)}}N_2\br{\mathbf{Q}_{u,j}^{(4)}}.\end{multline*}
\item If $\mathbf{P}_{u,i}^{(4)}=\mathbf{P}_{v,i}^{(4)}$, then $\mathbf{P}_{u,i}^{(5)}=\mathbf{P}_{v,i}^{(5)}$.
If $\mathbf{Q}_{u,i}^{(4)}=\mathbf{Q}_{v,i}^{(4)}$, then $\mathbf{Q}_{u,i}^{(5)}=\mathbf{Q}_{v,i}^{(5)}$.
\end{enumerate}
\bigskip
\item\textbf{Invariance from $L^2\br{\H_m^{\otimes h},\gamma_{n_0n_1}}$ to $\H_m^{\otimes h+n_0n_1}$}. From  item 1 and item 2 above, and  item 3 of \cref{fac:vecfun} and \cref{lem:randoperator}, we have
\[\sum_{\sigma}\influence_j\br{p_{u,i,\sigma}^{(5)}}\leq\tau N_2\br{\mathbf{P}_{u,i}^{(4)}}^2.\]
Similarly, we have
\[\sum_{\sigma}\influence_i\br{q_{u,i,\sigma}^{(5)}}\leq\tau N_2\br{\mathbf{Q}_{u,i}^{(4)}}^2.\]
For any $u\in[s]$, we apply \cref{lem:invariancejointgaussian} to $\br{\mathbf{P}_{u,i}^{(5)},\mathbf{Q}_{u,i}^{(5)}}$ with $n\leftarrow n_0n_1,h\leftarrow h,d\leftarrow d_2$,
$$\tau\leftarrow\tau_0=\max_u\set{\max\set{\tau N_2\br{\mathbf{P}_{u,i}^{(4)}}^2,\tau N_2\br{\mathbf{Q}_{u,i}^{(4)}}^2}~:~u\in[s]}$$
to get $\br{P_{u,i}^{(6)},Q_{u,i}^{(6)}}\in\H_m^{\otimes h+n_0n_1}\times \H_m^{\otimes h+n_0n_1}$ satisfying that

\bigskip
\begin{enumerate}
\item $\sum_{i=1}^t P_{u,i}^{(6)}=\id$ and $\sum_{i=1}^tQ_{u,i}^{(6)}=\id$.
\item For all $i,j\in[t]$ $$\Tr\br{\br{P_{u,i}^{(6)}\otimes Q_{u,j}^{(6)}}\psi_{AB}^{\otimes (n_0n_1+h)}}=\expec{}{\Tr\br{\br{\mathbf{P}_{u,i}^{(5)}\otimes\mathbf{Q}_{u,j}^{(5)}}\psi_{AB}^{\otimes h}}}.$$

\item For all $i\in[t]$ $$N_2\br{\mathbf{P}_{u,i}^{(5)}}=\nnorm{P_{u,i}^{(6)}}_2,N_2\br{\mathbf{Q}_{u,i}^{(5)}}=\nnorm{Q_{u,i}^{(6)}}_2.$$

\item For all $i\in[t]$ \begin{multline*}\abs{\expec{}{\frac{1}{m^h}\Tr~\zeta\br{\mathbf{P}_{u,i}^{(5)}}-\frac{1}{m^{n_0n_1+h}}\Tr~\zeta\br{P_{u,i}^{(6)}}}}\\\leq O\br{\br{3^{d_2}m^{d_2/2}d_2\sqrt{\tau_0}}^{2/3}};\end{multline*}

\begin{multline*}\abs{\expec{}{\frac{1}{m^h}\Tr~\zeta\br{\mathbf{Q}_{u,i}^{(5)}}-\frac{1}{m^{n_0n_1+h}}\Tr~\zeta\br{Q_{u,i}^{(6)}}}}\\\leq O\br{\br{3^{d_2}m^{d_2/2}d_2\sqrt{\tau_0}}^{2/3}}.\end{multline*}
\item If $\mathbf{P}_{u,i}^{(5)}=\mathbf{P}_{v,i}^{(5)}$, then $P_{u,i}^{(6)}=P_{v,i}^{(6)}$.
If $\mathbf{Q}_{u,i}^{(5)}=\mathbf{Q}_{v,i}^{(5)}$, then $Q_{u,i}^{(6)}=Q_{v,i}^{(6)}$.
\end{enumerate}
\bigskip

\item\textbf{Rounding to measurement operators}. Let $\pos{\br{P_{u,i}^{(6)}}}$ and $\pos{\br{Q_{u,i}^{(6)}}}$ be the matrices defined in Eq.\cref{eqn:geq0def}. Suppose

\[X_u=\sum_{i=1}^t\pos{\br{P_{u,i}^{(6)}}} ~\mbox{and}~Y_u=\sum_{i=1}^t\pos{\br{Q_{u,i}^{(6)}}}.\]
$$\br{\widetilde{P_{u,i}}}_{1\leq i\leq t}=\br{\sqrtpinv{X_u}\pos{\br{P_{u,1}^{(6)}}}\sqrtpinv{X_u},\dots,\sqrtpinv{X_u}\pos{\br{P_{u,t}^{(6)}}}\sqrtpinv{X_u}}$$
$$\br{\widetilde{Q_{u,i}}}_{1\leq i\leq t}=\br{\sqrtpinv{Y_u}\pos{\br{Q_{u,1}^{(6)}}}\sqrtpinv{Y_u},\dots,\sqrtpinv{Y_u}\pos{\br{Q_{u,t}^{(6)}}}\sqrtpinv{Y_u}}$$

It is easy to verify that $\br{\widetilde{P_{u,i}}}_{1\leq i\leq t}$ and $\br{\widetilde{Q_{u,i}}}_{1\leq i\leq t}$ are both sub-POVMs for $u\in[s]$.  Then
\begin{eqnarray*}
&&\abs{\Tr\br{\br{P_{u,i}^{(6)}\otimes Q_{u,j}^{(6)}}\psi_{AB}^{\otimes n_0n_1+h}}-\Tr\br{\br{\widetilde{P_{u,i}}\otimes \widetilde{Q_{u,j}}}\psi_{AB}^{\otimes n_0n_1+h}}}\\
&\leq&\abs{\Tr\br{\br{P_{u,i}^{(6)}\otimes \br{Q_{u,j}^{(6)}-\widetilde{Q_{u,j}}}}\psi_{AB}^{\otimes n_0n_1+h}}}+\abs{\Tr\br{\br{\br{P_{u,i}^{(6)}-\widetilde{P_{u,i}}}\otimes \widetilde{Q_{u,j}}}\psi_{AB}^{\otimes n_0n_1+h}}}\\
&\leq&\nnorm{P_{u,i}^{(6)}}_2\br{ \frac{3(t+1)}{m^{h+n_0n_1}}\sum_{i=1}^t\Tr~\zeta\br{Q_{u,i}^{(6)}} +6\br{ \frac{t}{m^{h+n_0n_1}}\sum_{i=1}^t\Tr~\zeta\br{Q_{u,i}^{(6)}} }^{\frac{1}{2}}}^{\frac{1}{2}}\\
&&+\br{ \frac{3(t+1)}{m^{h+n_0n_1}}\sum_{i=1}^t\Tr~\zeta\br{P_{u,i}^{(6)}} +6\br{ \frac{t}{m^{h+n_0n_1}}\sum_{i=1}^t\Tr~\zeta\br{P_{u,i}^{(6)}} }^{\frac{1}{2}}}^{\frac{1}{2}},
\end{eqnarray*}
\end{itemize}
where the second inequality follows from \cref{fac:cauchyschwartz} and the last inequality follows from \cref{lem:closedelta}.

Keeping track of the parameters in the construction, we are able to upper bound $\sum_{j=1}^t\frac{1}{m^{h+n_0n_1}}\Tr~\zeta\br{Q_{u,j}^{(6)}}$. The dependency of parameters is pictorially described in \cref{fig:dependence}. Choosing

\begin{equation}\label{eqn:paramters}
\delta=\epsilon^8/\br{10^{16}t^2s}, \tau=\epsilon^{12}/\br{s^2t^3\exp\br{\frac{\log m\log^2\frac{1}{\delta}}{\br{1-\rho}\delta}}}~\mbox{and}~ D=n_0n_1+h,
\end{equation}
we conclude the desired result.
\end{proof}

\newcommand{\rectab}[1]{\begin{tabular}{|c|}\hline#1\\\hline\end{tabular}}
\newcommand{\somespace}{5em}
\setlength{\tabcolsep}{1pt}
\begin{figure}\label{fig:dependence}
\begin{center}
\begin{codi}
\obj{
|(C)|\rectab{Regularity\\(\cref{lem:regular})}&&[\somespace]&[\somespace]&|(B)|\rectab{Smoothing: 1\\
(\cref{lem:smoothing of strategies})}\\
&|(H)|\rectab{$\epsilon$}&|(A)|\rectab{$\delta,\tau$ in Eq.~\cref{eqn:paramters}\\Given $m,s,t,\rho$}&&\\[8em]
&|(G)|\rectab{Multilinearize\\(\cref{lem:multiliniearization})}&|(F)|\rectab{Smoothing: 2\\(\cref{lem:smoothgaussian})}&&\\[2em]
|(E)|\rectab{$D=h+n_0\cdot n_1$}&&&&|(D)|\rectab{Dim reduction\\(\cref{lem:dimensionreduction})}\\
\mor H \mathrm{{determines}}:-> A \delta\leftarrow\delta :-> B;
\mor :B d\leftarrow d_1=\frac{{2\log^2(1/\delta)}}{{C\br{1-\rho}\delta}}:-> C;
\mor :C h\leq{\frac{2std_1}{\tau} }:-> E;
\mor A \epsilon\leftarrow\tau :-> C;
\mor [swap]:B d\leftarrow d_1=\frac{{2\log^2(1/\delta)}}{{C\br{1-\rho}\delta}} :-> D;
\mor A \delta\leftarrow\delta/2st^2:-> D;
\mor :D n_0={\frac{m^{O(h)}d_1^{O\br{d_1}}s^6t^{12}}{\delta^6}}:-> E;
\mor A \delta\leftarrow\delta:-> F {\rule{0pt}{1cm}d\leftarrow d_2=O\br{{\frac{\log^2\frac{1}{\delta}}{\delta\br{1-\rho}}}}}:-> G;
\mor A \delta\leftarrow\tau:-> G n_1=O\br{{\frac{d_2^2}{\tau^2}}}:-> E;
\end{codi}
\end{center}\caption{Dependency of parameters in the proof of \cref{lem:nijslem}}
\end{figure}
\section{Summary and open problems}\label{sec:openproblems}

In this work, we prove that if the players in a nonlocal game are provided with arbitrarily many copies of noisy MESs, then the game is decidable. We prove it by reducing the problem to the decidability of the quantum non-interactive simulation
of joint distributions and uses the framework in~[32]. To this end, we systematically generalize the theory of Boolean analysis to the space of matrices and the space of random matrices.

This work also raises many interesting open questions.

\begin{enumerate}
\item In this paper, we prove a quantum invariance principle for $C^3$ piecewise polynomial functions. Can we establish a quantum invariance principle for a larger class of functions? More specifically, can we prove a quantum analog of the classical invariance principle in~[40]?

\item As mentioned above, invariance principles have rich applications in theoretical computer science. Are there other applications of the quantum invariance principle established in this paper?

\item We essentially use the dimension reduction for polynomials in Gaussian spaces~[31] as an intermediate step. Is it possible to simplify the proof by proving a quantum dimension reduction directly?

\item Given a nonlocal game $G$ and a bipartite state $\psi$, we say $\br{G,\psi}$ is a {\em mono-state game} if the players in $G$ only share arbitrarily many copies of a bipartite state $\psi$. This paper proves that the mono-state games $\br{G,\psi}$ are decidable if $\psi$ is a noisy MES. It is known that the games are undecidable if $\psi$ is an EPR state because of Ji et al.'s breakthrough work~[47]. Due to PCP theorem~[2, 3] it is $\mathrm{NP}$-complete when $\psi$ is separable. Hence it is interesting to identify the hardness of the mono-state games $\br{G,\psi}$ for any given bipartite state $\psi$.

\item  Can we use the framework developed in this paper to design algorithms for other "tensored" quantities in quantum information theory and quantum complexity theory such as quantum channel capacities~[35], the regularizations of the various entanglement measures~[68], quantum information complexity~[80], etc.?

\item Is it possible to generalize our result to multiplayer nonlocal games?  Note that the decidability of non-interactive simulations of $k$-partite distributions for $k\geq 3$ is still open~[32].
\end{enumerate}

\section{Smoothing operators}\label{sec:smoothoperators}
The main lemma in this section is the following.

\begin{lemma}\label{lem:smoothing of strategies}
Given parameters $0\leq\rho<1$, $0<\delta<1$, integer $n>0, m>1$ an $m$-dimensional noisy MES $\psi_{AB}$  with the maximal correlation $\rho=\rho\br{\psi_{AB}}$, there exists $d=d\br{\rho,\delta}$ and a map $f:\H_m^{\otimes n}\rightarrow \H_m^{\otimes n},$ such that for any $P\in\H_m^{\otimes n}, Q\in\H_m^{\otimes n}$ satisfying $0\leq P\leq \id$ and $0\leq Q\leq \id$, the operators $P^{(1)}=f\br{P}$ and $Q^{(1)}=f\br{Q}$ satisfy that

\begin{enumerate}
\item $0\leq P^{(1)}\leq \id~\mbox{and}~0\leq Q^{(1)}\leq \id;$
%\item $\Tr~P^{(1)}=\Tr~P~\mbox{and}~\Tr~Q^{(1)}=\Tr~Q;$
\item $\nnorm{P^{(1)}}_2\leq\nnorm{P}_2~\mbox{and}~\nnorm{Q^{(1)}}_2\leq\nnorm{Q}_2;$
\item $\abs{\Tr\br{\br{P^{(1)}\otimes Q^{(1)}}\psi^{\otimes n}_{AB}}-\Tr\br{\br{P\otimes Q}\psi^{\otimes n}_{AB}}}\leq\delta,$
\item $\nnorm{\br{P^{(1)}}^{>d}}^2_2\leq\delta~\mbox{and}~\nnorm{\br{Q^{(1)}}^{>d}}^2_2\leq\delta,$