\\&\le \frac{\dout^4+ 6\din^3+2\din^2\dout m^2+2\din^2\dout \eta^2+ 11\din^2+ 10\din \dout m^2+10\din\dout \eta^2 }{\dout^2\din(\din+1)(\din+2)(\din+3)}
\\&+ \frac{6\din + \dout^2m^4+2\dout^2\eta^2+ 12\dout m^2+ 40\dout^2m\eta^3 +81\dout^2\eta^4+12 \dout \eta^2   }{\dout^2\din(\din+1)(\din+2)(\din+3)}- \left(\frac{m^2+\eta^2}{\din(\din+1)}+\frac{1}{\dout}\right)^2
%\\&-\frac{(d+2)(d+3)(m^4 +2(d+1+\eta^2)m^2+d^2+2d+1+2\eta^2(1+d)+\eta^4 )}{d^2(d+1)^2(d+2)(d+3)}
\\&\le \left(\frac{80\din^2\eta^4+10\din^2m^2\eta^2+40\din^2\eta^3m}{\din^2(\din+1)^2(\din+2)(\din+3)}\right).
%\\&\le  \frac{     16\eta^2\sqrt{m}}{d^2(d+1)^2}
\end{align*}

Therefore the upper bound on the variance becomes using the inequalities $(m^2+\eta^2)^2\ge 4m^2\eta^2$ and  $(m^2+\eta^2)^2\ge 2m\eta^{3}$
(successive AM-GM):

\begin{align*}
\frac{\var(X)}{\ex{X}^2}&\le  \left( \frac{80\din^2\eta^4+10\din^2m^2\eta^2+40\din^2\eta^3m}{(\din+2)(\din+3)(\eta^2+m^2  )^2} \right)
\\&\le 80\frac{\din^2\eta^4}{\din^2\eta^4}+ 10\frac{\din^2m^2\eta^2}{4\din^2m^2\eta^2}+40\frac{\din^2\eta^3m}{2\din^2m\eta^{3}}%+C\frac{m^3d\sqrt{d}}{2d^2m^{3}\eta}
\le 105.
\end{align*}

There is an incoherent ancilla-free algorithm using a number of measurements satisfying

\begin{align*}
\end{align*}

to distinguish between $\cN=\cD$ or $\dd(\cN,\cD)>\eps$ with a probability of success at least $2/3$.

Complexity. We start by showing that  Alg. <ref> uses $\cO(\din^2\dout^{1.5}/\eps^2)$  measurements. Note that Alg. <ref> requires $\cO(\sqrt{\dout}\log(3M)/\eta^2)$ to test whether a $\dout$-dimensional quantum state $\rho$ satisfies $\rho= \frac{\dI}{\dout}$ or $\left\|\rho-\frac{\dI}{\dout}\right\|_2\ge \eta$ with an error probability $1/{(3M)}$. We apply this test for the state $\cN(\proj{\phi})$ , which is a $\dout$-dimensional quantum state, and $\eta= \frac{\eps}{2\sqrt{\dout}\din}$. So the testing identity of states algorithm will use a number of measurements $\cO(\din^2\dout^{1.5}\log(3M)/\eps^2)$. Since we repeat this test a number of $M=\cO(1)$ times, the total number of measurements is $\cO(\din^2\dout^{1.5}/\eps^2)$.

Correctness. It remains to show that Alg. <ref> is $1/3$-correct. For this, we need to control two error probabilities. The first one, under the null hypothesis $H_0$, the channel $\cN=\cD$ so for all $k\in [M]$, $\cN(\proj{\phi_k}))=\frac{\dI}{\dout} $. Hence, for all the quantum states test we are under the null hypothesis $h_0$. Therefore

\begin{align*}
\mathds{P}_{H_0}(\text{error}) &= \mathds{P}_{H_0}(\exists k\in [M]: i_k=1)
\\&\le\sum_{k=1}^M\mathds{P}_{h_0}(i_k=1)\le\sum_{k=1}^M\frac{1}{3M}=\frac{1}{3}.
\end{align*}

The second error probability concerns the alternate hypothesis $H_1$. In this case, the channel $\cN$ is $\eps$-far from the depolarizing channel $\cD$. For a given $k\in [M]$, let us lower bound the probability of being under $h_1$ at step $k$ of the algorithm. Let   $X_k=\left\|\cN(\proj{\phi_k}) -\frac{\dI}{\dout}\right\|_2^2$. Recall that Thm. <ref> says:

\begin{align*}
\var(X_k)\le 105\ex{X_k}^2  % \cO\left(\frac{\ex{X_k}^2}{\sqrt{d}d\|\cJ_\cN-\dI/d^2\|_2}\right)= \cO\left(\frac{\ex{X_k}^2}{\dd(\cN,\cD)}\right)=\cO\left(\frac{\ex{X_k}^2}{\eps}\right).
\end{align*}

Therefore, the  Paley-Zygmund inequality implies

\begin{align*}
\pr{X_k\ge \frac{1}{2}\ex{X_k}}&\ge 1-\frac{1}{\frac{1}{4}\frac{\ex{X_k}^2}{\var(X_k)}+1}\ge 1-\frac{1}{\frac{1}{8\times 105}+1}
\ge 10^{-3}.
\end{align*}

Recall also that $\ex{X_k}= \ex{ \left\|\cN(\proj{\phi_k}) -\frac{\dI}{d}\right\|_2^2}\ge \frac{\eps^2}{2\din^2\dout}$ (Ineq. <ref>). Therefore, with a probability at least $10^{-3}$, we have $\left\|\cN(\proj{\phi_k}) -\frac{\dI}{\dout}\right\|_2\ge \frac{\eps}{2\din\sqrt{\dout}}$ which means we are under the alternate hypothesis $h_1$. Denote the good event of $E_k=\left\{\left\|\cN(\proj{\phi_k}) -\frac{\dI}{\dout}\right\|_2
\ge \frac{\eps}{2\din\sqrt{\dout} } \right\}$, the probability of error under $H_1$ can be controlled as follows:

\begin{align*}
\mathds{P}_{H_1}(\text{error})&= \mathds{P}_{H_1}(\forall k \in [M]: i_k=0)
= \prod_{k=1}^{M} \mathds{P}_{H_1}(i_k=0)
%\le  \pr{\text{error at step } 1}^{k}
\\&\le \prod_{k=1}^{M} \left( \mathds{P}_{H_1}(i_k=0 | E_k)\pr{E_k}+\mathds{P}_{H_1}(i_k=0| \bar{E}_k)\pr{\bar{E}_k}\right)
\\&\le \prod_{k=1}^{M} \left( \mathds{P}_{h_1}(i_k=0 )\pr{E_k}+\pr{\bar{E}_k}\right)
\\&\le \prod_{k=1}^{M} \left( \mathds{P}_{H_1}(i_k=0 | E_k)\pr{E_k}+1-\pr{E_k}\right)
\\&=\prod_{k=1}^{M} \left( 1-\pr{E_k}\mathds{P}_{h_1}(i_k=1 | E_k)\right)
%  \\&\le  \prod_{k=1}^{M} \left( \left(1-\frac{1}{3M}\cdot\pr{E_k}+\pr{\bar{E}_k}\right)
\\&\le \left( 1-10^{-3}\cdot \left(1-\frac{1}{3M}\right)  \right)^{M}
\le \left(   1-\frac{10^{-3}}{2} \right)^{M}
\le \frac{1}{3}
%\left(1-\frac{\eps}{8C}\right)/ \frac{1}{3M}
\end{align*}

for $M=2200=\cO(1)$. This concludes the correctness of  Alg. <ref>.

§ LOWER BOUNDS FOR TESTING IDENTITY TO THE DEPOLARIZING CHANNEL

§.§ Proof of Thm. <ref>

Let $\eps\le 1/32$, $\din \ge 80$ and $\dout\ge 10$. [We didn't try to optimize these conditions.]  Any incoherent ancilla-assisted non-adaptive algorithm for testing identity to the depolarizing channel (in both the trace and diamond distances) requires, in the worst case, a number of measurements

\begin{align*}
\end{align*}

Under the null hypothesis $H_0$ the quantum channel is $\cN(\rho)=\cD(\rho)= \tr(\rho)\frac{\dI}{\dout}$. Under the alternate hypothesis $H_1$, we choose the quantum channel $\cN\sim \cP$ of the form:

\begin{align*}
\cN(\rho)= \tr(\rho) \frac{\dI}{\dout} +\frac{\eps}{\dout} \bra{\bar{w}}\rho \ket{\bar{w}} U
\end{align*}

where $\ket{w}= W\ket{0}$, $W \sim \Haar(\din)$, and $U$ satisfies

\begin{align*}
\begin{cases*}
U_{x,x}=0  & for all   $x\in [\dout]$, \\
U_{y,x}=\bar{U}_{x,y} \sim  \cN_c(0, \sigma^2) =  \cN(0, \sigma^2/2)+i\, \cN(0, \sigma^2/2) &  for all   $x<y\in [\dout]$,
\end{cases*}
\end{align*}

where the parameter $\sigma$ would be chosen later and we condition on the event
\[\cG=\{\|U\|_1\ge \dout, \|U\|_\infty \le 32\}.\]

We call this distribution $\cP$ and use the notation $(w,U)\sim \cP$. If we don't condition on the event $\cG$, the distribution of $U$ is denoted $\cP_0$ and we write $U\sim \cP_0$. Random constructions with Gaussian random variables were used for proving lower bounds by Chen et al., 2022, Chen et al., 2022.
Note that $\cN$ is trace preserving since $\tr(U)=0$. In order to prove that $\cN$ is a quantum channel, it remains to show that $\cN$ is completely positive which is equivalent to show that  the corresponding Choi matrix is positive semi-definite. For this we can express the Choi state of the channel $\cN$:

\begin{align*}
\cJ_\cN&= \frac{\dI}{\din \dout}+ \frac{\eps}{\din \dout} \sum_{i,j=1}^{\din} \ket{i}\bra{j} \otimes\bra{0}W^\top \ket{i}\bra{j} \bar{W}\ket{0} U
\\&=\frac{\dI}{\din \dout}+ \frac{\eps}{\din \dout} \sum_{i,j} \ket{i}\bra{j} \otimes\bra{i}W \ket{0}\bra{0} W^{\dagger}\ket{j} U
\\&=\frac{\dI}{\din \dout}+ \frac{\eps}{\din \dout} W \ket{0}\bra{0} W^{\dagger}\otimes U
\\&=\frac{\dI}{D}+ \frac{\eps}{D}  \ket{w}\bra{w} \otimes U
\end{align*}

where $D=\din \dout$.

Observe that $ \|\proj{w}\otimes U  \|_\infty  = \|U \|_\infty \le 32 $  thus $\cJ_\cN\ge 0$ if $\eps \le 1/32$. So under the event $\cG$, the map $\cN$ is a quantum channel. The parameter $\sigma$ should be chosen so that $\dd(\cN,\cD)\ge \eps$. Recall that $\ket{w}= W\ket{0}$, the definition of the diamond distance implies

\begin{align*}
%d_\diamond(\cN,\cM):= -\dI\otimes\cM(\proj{\phi})
\dd(\cN,\cD)&\ge \td(\cN, \cD)= \max_{\rho }\|(\cN-\cD)(\rho) \|_1
\\&\ge \|(\cN-\cD)(\proj{\bar{w}})\|_1
=\frac{\eps}{\dout}\|U\|_1\ge \eps
\end{align*}

where we use the fact that under the event $\cG$ we have $\|U\|_1\ge \dout$.
Note that the lower bound we prove in this theorem holds for the stronger condition given by the  trace distance.

Now we move to show that the event $\cG$ occurs with high probability.

There is a constant $c>0$ such that we have:

\begin{align*}
\pr{|\|U\|_1-\ex{\|U\|_1}|>s }\le \exp\left(-\frac{cs^2}{\dout\sigma^2}\right)
\end{align*}

The function $U\mapsto \|U\|_1$ is $\sqrt{\dout}$-Lipschitz w.r.t. the Hilbert-Schmidt norm. Indeed, by the triangle inequality and the Cauchy Schwarz inequality $|\|U\|_1-\|V\|_1|\le \|U-V\|_1\le \sqrt{\dout}\|U-V\|_2$. The concentration of Lipschitz functions of Gaussian random variables <cit.>  yields exactly the desired statement.

Next, we need a lower bound on the expectation of $\|U\|_1$. By the Hölder's inequality:

\begin{align*}
\ex{\|U\|_1}\ge \sqrt{\frac{\ex{\|U\|_2^2}^3}{\ex{\|U\|_4^4}}}\ge \sqrt{\frac{(\dout^2\sigma^2)^3}{4\dout^3\sigma^4}}= \frac{\dout\sqrt{\dout}\sigma}{2}.
\end{align*}

It is sufficient to choose $\sigma=\frac{4}{\sqrt{\dout}}$ so that $\ex{\|U\|_1}\ge 2\dout$
and by Lem. <ref>, we have $\|U\|_1\ge \dout$ with a probability  $1-\exp(-\Omega(\dout^2))$.
It remains to see that, for this choice of $\sigma= \frac{4}{\sqrt{\dout}}$, the event $\{\|U\|_\infty \le 32\}$
also occurs with high probability.  Indeed,

let $\cS$ be a $1/4$-net of $\bS^{\dout}$ of size at most $8^{\dout}$. By the union bound:

\begin{align*}
\pr{\|U\|_\infty >32}&=\pr{\exists \phi\in \bS^{\dout}: \bra{\phi} U\ket{\phi}=\|U\|_\infty, \|U\|_\infty >32 }
\\&\le \pr{\exists \phi\in \cS: \bra{\phi} U\ket{\phi}>\frac{1}{2}\|U\|_\infty, \|U\|_\infty >32 }
\\&\le |\cS|\pr{ \bra{\phi} U\ket{\phi}>16}
\le 8^{\dout} e^{-8\dout}\le e^{-4\dout}.
\end{align*}

Finally, with a probability at least $1-\exp(-\Omega(\dout^2))-\exp(-\Omega(\dout))$  the event $\cG$ is satisfied and we have a quantum channel $\cN$ that is $\eps$-far in the diamond distance  from the depolarizing channel $\cD$. A $1/3$-correct algorithm $\cA$ should distinguish between the channels $\cN$ and $\cD$ with a probability of error at most $1/3$. Let $N$ be a sufficient number of measurements for this task and $I_1,\dots, I_N$ be  the observations of the algorithm $\cA$. The Data-Processing inequality applied on the $\TV$-distance gives LeCam's method [LeCam, 1973]:

\begin{align*}
\TV\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1}^{I_1,\dots, I_N}\right)&\ge  \TV\left(\Ber(\mathds{P}_{H_0}(\cA=1))\| \Ber(\mathds{P}_{H_1}(\cA=1))\right)
\\&\ge \TV(\Ber(1/3)\| \Ber(2/3))= \frac{1}{3}.
\end{align*}

Now, we need to upper bound this $\TV$ distance with an expression involving $N, \din, \dout$ and $\eps$.

Upper bound on the $\TV$ distance.
The non-adaptive algorithm $\cA$ would choose at step $t$ the input $\rho_t$ and the measurement device $\cM_t=\{\lambda_i^t \proj{\phi_i^t}\}_{i\in \cI_t}$. Observe that we can always reduce w.l.o.g. to such a POVM.
Under the null hypothesis $H_0$, the quantum channel $\cN=\cD$ so the probability distribution of the outcomes is exactly:

\begin{align*}
\mathds{P}_{H_0}^{I_1,\dots, I_N}= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cD (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N} .
\end{align*}

On the other hand, under the alternate hypothesis $H_1$, the probability of the outcomes is exactly:

\begin{align*}
\mathds{P}_{H_1}^{I_1,\dots, I_N}= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cN (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N}
%\left\{\mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \frac{\lambda_{i_t}^t}{\dout^N}\left(1+\eps \bra{w}\rho_t\ket{w} \bra{\phi_{i_t}^t}U\ket{\phi_{i_t}^t}  \right) \right\}_{i_1,\dots, i_N}
\end{align*}

Recall that $D=\din \dout$ and

\begin{align*}
\cJ_\cD= \frac{\dI}{D} ~~\text{ and }~~\cJ_\cN= \frac{\dI}{D}+ \frac{\eps}{D}  \proj{w} \otimes U.
\end{align*}

We can suppose w.l.o.g. that each input state is pure because of the convexity of the $\TV$ distance. That is, for $t\in [N]$, we write $\rho_t= \proj{\psi_t}$. Moreover, we can write each rank one input state and measurement vector as follows:

\begin{align*}
\ket{\psi_t}= A_t\otimes \dI \ket{\Psi_{\din}} ~~\text{ and }~~\ket{\phi_{i_t}^t}=  B_{i_t}^t\otimes \dI \ket{\Psi_{\dout}}
\end{align*}

where $\ket{\Psi_d}= \frac{1}{\sqrt{d} } \sum_{i=1}^{d} \ket{ii}$ and the matrices $A_t \in \dC^{\danc \times \din }$ and $B_{i_t}^t \in \dC^{\danc \times \dout }$ verify:

\begin{align*}
\tr(A_tA_t^\dagger )= \din  ~~\text{ and }~~  \tr(B_{i_t}^tB_{i_t}^{t,\dagger} )= \dout.
\end{align*}

Note that we have for all $t$, for all $X\in \dC^{\danc\otimes \danc}$ wa have $\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger}XB_{i_t}^{t} = \dout\tr(X)\dI_{\dout}$. Indeed, the condition of the POVM $\cM_t$ implies:

\begin{align*}
X\otimes \dI=    X\otimes \dI\sum_{i_t}\lambda_{i_t}^t \proj{\phi_{i_t}^t} =  \sum_{i_t}\lambda_{i_t}^t XB_{i_t}^t\otimes \dI \proj{\Psi_{\dout}} B_{i_t}^{t, \dagger}\otimes\dI
\end{align*}

hence by taking the partial trace

\begin{align*}
\tr(X) \dI = \frac{1}{\dout}\sum_{i_t, i, j}\lambda_{i_t}^t \bra{j}  B_{i_t}^{t, \dagger}X B_{i_t}^{t} \ket{i}  \ket{i}\bra{j}.
\end{align*}

\begin{align*}
\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger}XB_{i_t}^{t} = \dout\tr(X)\dI_{\dout}.
\end{align*}

By taking $X=\dI$  and the partial trace on the second system we have

\begin{align*}
\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t} B_{i_t}^{t, \dagger} =\dout^2 \dI_{\danc}.
\end{align*}

Now we can re-write the  distribution  of the observations under the null hypothesis as follows:

\begin{align*}
\mathds{P}_{H_0}^{I_1,\dots, I_N}&= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cD (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\cJ_\cD (A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&= \left\{\prod_{t=1}^N\frac{\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t} \otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&= \left\{\prod_{t=1}^N\frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})
\right\}_{i_1,\dots, i_N} ,
\end{align*}

and under the alternate hypothesis as follows:

\begin{align*}
\mathds{P}_{H_1}^{I_1,\dots, I_N}&= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cN (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\cJ_\cN (A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\left(\frac{\dI}{D}+ \frac{\eps}{D}  \proj{w} \otimes U \right)(A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N \left( \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})+ \frac{\eps\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}\right)
\right\}_{i_1,\dots, i_N}
\end{align*}

So, we can express the $\TV$ distance as follows:

\begin{align*}
& 2\TV\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1}^{I_1,\dots, I_N}\right)
\\&=\sum_{i_1,\dots, i_N}\Bigg| \mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \left( \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})+ \frac{\eps\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}\right)
\\& \qquad\qquad \qquad\quad\ \ -\prod_{t=1}^N\frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\Bigg|
\\&= \mathds{E}_{\le N}\left| \mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \left(1+\eps\dout \frac{\bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right) -1\right|
\\&= \mathds{E}_{\le N}\left| \mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \left(1+\eps\cdot  \frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right) -1\right|
\end{align*}

where we use the notation $\mathds{E}_{\le N}(X(i_1,\dots, i_N))= \sum_{i_1,\dots, i_N}\left(\prod_{t=1}^N \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\right)X(i_1,\dots, i_N)$.
Let $u$ be a standard Gaussian vector  such that $\ket{w}=\frac{\ket{u}}{\|u\|_2}$. We condition on the event $\cE$ that $u$ satisfies:

* $\|u\|_2 \;\ge \sqrt{\frac{1}{6}\din}$    and

* $\forall t\in [N]:P_u^t\le \frac{(7\log(N))^4}{\din^4 \dout}$

where $P_u^t$ is defined as

\begin{align*}
P^t_w&= \sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}\left(\frac{|\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w}|^4}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right)
\\ P_u^t&= \sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2\din^4}\left(\frac{|\bra{u}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{u}|^4}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right).
\end{align*}

Note that under the event $\cE$, we have $P_w^t\le 6^4 P_u^t $. We claim that for  $\din \ge 80$, we have with probability at least $9/10$, the event $\cE$ is satisfied. The proof of this claim is deferred to Lemma <ref>.

Now, we can distinguish whether the event $\cE$ is verified or not in the $\TV$ distance. Let
$$\Psi_{i,w, U}=\prod_{t=1}^N \left(1+\eps\cdot \Phi^{t,i_t}_{w, U} \right)\quad \text{ where }\quad  \Phi^{t,i_t}_{w, U}=\frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}.  $$

By the triangle inequality:

\begin{align*}
&\mathds{E}_{\le N}\left| \mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \left(1+\eps\cdot \frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}  \right) -1\right|
\\ &\le    \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\cE\}(\Psi_{i,w, U} -1)\right]\right|+  \mathds{E}_{\le N}
\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\bar{\cE}\}(\Psi_{i,w, U} -1)\right]\right|
\\ &\le    \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\cE\}(\Psi_{i,w, U} -1)\right]\right|+  \mathds{E}_{\le N}
\mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\bar{\cE}\}(\Psi_{i,w, U} +1)\right]
%  \\&\le \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP\\ |\cE}}\left[\prod_{t=1}^N \left(1+\eps \bra{w}\rho_t\ket{w} \bra{\phi_{i_t}^t}U\ket{\phi_{i_t}^t}  \right) -1\right]\right|+   \mathds{E}_{\substack{(w,U)\sim\cP\\ |\bar{\cE}}}\mathds{E}_{\le N}\left[\prod_{t=1}^N \left(1+\eps \bra{w}\rho_t\ket{w} \bra{\phi_{i_t}^t}U\ket{\phi_{i_t}^t}  \right) +1\right]
\\&= \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\cE\}(\Psi_{i,w, U} -1)\right]\right|+ 2\pr{\Bar{\cE}}
\end{align*}

where we use the fact that $\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger}XB_{i_t}^{t} = \dout\tr(X)\dI$ and

\begin{align*}
\mathds{E}_{\le N}\Psi_{i,w, U} &= \sum_{i_1,\dots, i_N}\left( \prod_{t=1}^N\frac{\lambda_{i_t}^t}{D\dout} \cdot \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\right)\prod_{t=1}^N \left(1+\eps\cdot \frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right)
\\&= \prod_{t=1}^N \sum_{i_t}\left(  \frac{\lambda_{i_t}^t}{D\dout} \cdot \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})+ \frac{\eps\lambda_{i_t}^t}{D\dout}\cdot \tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U) \right)
\\&= \prod_{t=1}^N \left(1+\frac{\eps}{D} \cdot\tr(A_t  \proj{w} A_t^\dagger )\tr(  U)\right)=1.
\end{align*}

It remains to upper bound the expectation $\mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[ \bm{1}\{\cE\}(\Psi_{i,w, U} -1)\right]\right|$. For this, we follow [Bubeck et al., 2020] and apply the Cauchy Schwarz inequality and Hölder's inequality:

\begin{align*}
& \left( \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[\bm{1}\{\cE\}(\Psi_{i,w, U}-1)\right]\right|\right)^2+\pr{\cE}^2
\\&\le \mathds{E}_{\le N}\left( \mathds{E}_{\substack{(w,U)\sim\cP}}\left[\bm{1}\{\cE(w)\}(\Psi_{i,w, U}-1)\right]\right)^2+\pr{\cE}^2
\\&= \mathds{E}_{\le N} \mathds{E}_{\substack{(w,U)\sim\cP}}\mathds{E}_{\substack{(z,V)\sim\cP}}\bm{1}\{\cE(w)\}\Psi_{i,w, U}\bm{1}\{\cE(z)\}\Psi_{i,z, V}
\\&\le  \mathds{E}_{\substack{(w,U)\sim\cP}}\bm{1}\{\cE(w)\}\mathds{E}_{\substack{(z,V)\sim\cP}}\bm{1}\{\cE(z)\} \prod_{t=1}^N \mathds{E}_{i_t}\left(1+\eps \cdot\Phi^{t,i_t}_{w, U}\right)\left(1+\eps \cdot\Phi^{t,i_t}_{z, V} \right)
\\&=  \mathds{E}_{\substack{(w,U)\sim\cP}}\bm{1}\{\cE(w)\}\mathds{E}_{\substack{(z,V)\sim\cP}}\bm{1}\{\cE(z)\}\prod_{t=1}^N \left(1+\eps^2\cdot \mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}\Phi^{t,i_t}_{z, V} \right) ~~~~  (\text{ because } ~~\mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}=0)
\\&\le \max_{1\le t \le N} \mathds{E}_{\substack{(w,U)\sim\cP}}\bm{1}\{\cE(w)\}\mathds{E}_{\substack{(z,V)\sim\cP}}\bm{1}\{\cE(z)\}\left(1+\eps^2 \cdot \mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}\Phi^{t,i_t}_{z, V} \right)^N
% \\&\le  \mathds{E}_{\substack{U\sim\cP}}\mathds{E}_{\substack{V\sim\cP}} \prod_{t=1}^N \left(1+\eps^2 \left(\frac{20\log(9N)}{\din}\right)^2 \left|\sum_{i_t}\frac{\lambda^t_{i_t}}{\dout}\bra{\phi_{i_t}^t}U\ket{\phi_{i_t}^t}    \bra{\phi_{i_t}^t}V\ket{\phi_{i_t}^t}\right|  \right)
\\&\le  \frac{1}{\pr{\cG}^2}\max_{1\le t\le N} \mathds{E}_{U,V\sim \cP_0} \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\}\left(1+\eps^2 \cdot \left|\mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}\Phi^{t,i_t}_{z, V}\right| \right)^N
\\&\le  \frac{1}{(1-e^{-\Omega(\dout)})^2}\max_{1\le t\le N} \mathds{E}_{U,V\sim \cP_0} \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\}\left(1+\eps^2\cdot \left|\mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}\Phi^{t,i_t}_{z, V}\right| \right)^N
\end{align*}

Note that at the last two inequalities, we don't require anymore that $U$ satisfies $\|U\|_\infty\le 32 $ and $\|U\|_1\ge \dout$.  This is possible because the integrand is positive and $\pr{\cG}\ge 1-e^{-\Omega(\dout)}$.

For $t\in [N]$, let $Z_t$ be the polynomial in $\{U_{i,j},V_{i,j}\}_{i,j=1}^{\dout}$ defined as follows:

\begin{align*}
Z_t&=\eps^2 \mathds{E}_{i_t} \Phi^{t,i_t}_{w, U}\Phi^{t,i_t}_{z, V}
\\&=\eps^2 \sum_{i_t }\left( \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\right) \left(\frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)\left(\frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{z} A_t^\dagger B_{i_t}^{t}  V)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)
\\&=\eps^2 \sum_{i_t }\left( \frac{\lambda_{i_t}^t}{D\dout} \right) \left(\frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)\tr(B_{i_t}^{t,\dagger}A_t  \proj{z} A_t^\dagger B_{i_t}^{t}  V)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)
\end{align*}

Note that $Z_t$ is a polynomial of degree $2$ of expectation $0$. The Hypercontractivity <cit.> implies for all $k\in \{1,\dots,N\}$:

\begin{align*}
\ex{|Z_t|^{k}}\le k^k  \ex{Z_t^{2}}^{k/2}.
\end{align*}

This means that we only need to control the second moment of $Z_t$. We have:

\begin{align*}
\mathds{E}_{U,V}(Z_t^{2})= \eps^4  \mathds{E}_{U,V}\Bigg[\sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}  &\left(\frac{\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)\tr(B_{i_t}^{t,\dagger}A_t  \proj{z} A_t^\dagger B_{i_t}^{t}  V)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)
\\&\cdot\left(\frac{\tr(B_{j_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{j_t}^{t}  U)\tr(B_{j_t}^{t,\dagger}A_t  \proj{z} A_t^\dagger B_{j_t}^{t}  V)}{\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})}\right)\Bigg].
\end{align*}

Let $\Xi_{i_t, j_t}(w)= \mathds{E}_U \big[\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)\tr(B_{j_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{j_t}^{t}  U)\big]$, we have :

\begin{align*}
\mathds{E}_{U,V}(Z_t^{2}) =  \eps^4 \sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}  \left(\frac{\Xi_{i_t, j_t}(w)\Xi_{i_t, j_t}(z)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})}\right)
\end{align*}

For given $i_t, j_t$, we can upper bound the expectation $\Xi_{i_t, j_t}$:

\begin{align*}%\label{expectation-U}
\Xi_{i_t, j_t}( w ) &= \mathds{E}_U \big[\tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  U)\tr(B_{j_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{j_t}^{t}  U)\big] \notag
\\&= \sum_{x,y,x',y'} \ex{U_{x,y}U_{x',y'}} \tr(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} \ket{x}\bra{y})\tr(B_{j_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{j_t}^{t}  \ket{x'}\bra{y'}) \notag
\\&\le  \frac{16}{\dout}\sum_{x,y} \bra{w}A_t^\dagger B_{i_t}^t \proj{x} B_{j_t}^{t,\dagger}A_t  \ket{w} \bra{w} A_t^\dagger B_{j_t}^{t}  \proj{y}B_{i_t}^{t,\dagger}A_t  \ket{w} \notag  %+\dots ~~~~\text{the other expression is similar with bars} \notag
\\&= \frac{16}{\dout}\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w} \bra{w} A_t^\dagger B_{j_t}^{t}B_{i_t}^{t,\dagger}A_t  \ket{w} \notag%+\dots \notag
\\&= \frac{16}{\dout}|\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w}|^2 %+\dots
\end{align*}

Therefore we can  upper bound the expectation of $Z_t^2$ as follows:

\begin{align*}
\mathds{E}_{U,V}(Z_t^{2}) &=  \eps^4 \sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}  \left(\frac{\Xi_{i_t, j_t}(w)\Xi_{i_t, j_t}(z)}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})}\right)
\\&= \eps^4   \left(\frac{ 16^2}{\dout^2}\right)\sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}\left(\frac{|\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w}|^2|\bra{z}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{z}|^2}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right)
%\\&\le \frac{C\eps^4\log(N)^4}{\din^4\dout^3}
\end{align*}

This implies an upper bound for every moment, that is for $k=1, \dots, N$, we have:

\begin{align*}
& \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\}\mathds{E}_{U,V}(|Z_t|^{k})    \\&\le \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\} k^k  \Bigg[\eps^4   \left(\frac{16^2}{\dout^2}\right)\sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}\left(\frac{|\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w}|^2|\bra{z}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{z}|^2}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right)\Bigg]^{k/2}
\\&\le k^k  \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\}\Bigg[\eps^4   \left(\frac{ 16^2}{\dout^2}\right)\sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2}\left(\frac{|\bra{w}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{w}|^4+|\bra{z}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{z}|^4}{2\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right)\Bigg]^{k/2}
\\&= k^k \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\} \Bigg[\eps^4   \left(\frac{ 16^2}{\dout^2}\right)\frac{(P_w^t +P_z^t)}{2} \Bigg]^{k/2}
\\&\le k^k \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\} \Bigg[\eps^4   \left(\frac{ 16^2\cdot 6^4}{\dout^2}\right)\frac{(P_u^t +P_v^t)}{2} \Bigg]^{k/2}
\\&\le k^k \mathds{E}_{\substack{w,z}}\bm{1}\{\cE(w)\}\bm{1}\{\cE(z)\} \Bigg[\eps^4   \left(\frac{ 16^2\cdot 6^4}{\dout^2}\right)  \left( \frac{(7\log(N))^4}{\din^4\dout}\right) \Bigg]^{k/2}
\le k^k  \Bigg[ \frac{C\eps^4\log(N)^4}{\din^4\dout^3}\Bigg]^{k/2}
\end{align*}

where $C>0$ is a universal constant and  we used that we are under the events $\cE(w)$ and $\cE(z)$.

Now, grouping the lower bound and upper bounds on the $\TV$ distance, we obtain:

\begin{align*}
(1-e^{-\Omega(\dout)})^2\left( \frac{7^2}{15^2}+\frac{9^2}{10^2}\right)&\le  (1-e^{-\Omega(\dout)})^2 \left[\left(2\TV\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1}^{I_1,\dots, I_N}\right)-2\pr{\bar{E}}   \right)^2+\pr{\cE}^2\right]
\\&\le (1-e^{-\Omega(\dout)})^2 \left[\left( \mathds{E}_{\le N}\left| \mathds{E}_{\substack{(w,U)\sim\cP}}\left[\bm{1}\{\cE\}(\Psi_{i,w, U}-1)\right]\right|\right)^2+\pr{\cE}^2\right]
\\&\le \max_t\ex{(1+|Z_t|)^N}\\&\le  \max_t \sum_{k=0}^N\binom{N}{k} k^k \left(\frac{C\eps^4\log(N)^4}{\din^4\dout^3}\right)^{k/2}
\le \sum_{k=0}^N  \left(\frac{C' N\eps^2\log(N)^2}{\din^{2}\dout^{1.5}}\right)^{k}
\end{align*}

where we used $\binom{N}{k}\le \frac{N^ke^k}{k^k}$ and $C'=\sqrt{C}e$. If $N\log(N)^2\le \frac{\din^{2}\dout^{1.5}}{101C'\eps^2}$ the  RHS is upper bounded by $\sum_{k\ge 0}\frac{1}{101^k}= 1.01$ but the LHS is at least $(1- e^{-\Omega(\dout)})^2\left( \frac{7^2}{15^2}+\frac{9^2}{10^2}\right)\ge 1.02$ for $\dout\ge \Omega(1)$  which is a contradiction. Hence $N\log(N)^2\ge \frac{\din^{2}\dout^{1.5}}{101C'\eps^2}$ and finally:

\begin{align*}
N\ge \Omega\left(\frac{\din^{2}\dout^{1.5}}{\log(\din\dout/\eps)^2\eps^2}\right).
\end{align*}

We move to prove our claim:

Let $\din \ge 80$.   We have with probability at least $9/10$, the event $\cE$ is satisfied.

Fix $t\in [N]$,  denote $(i,j)=(i_t,j_t)$, $X_i= B^\dagger_i A_t$ and recall that $\ket{w}=\frac{\ket{u}}{\|u\|_2}$ such that $u$ is a  standard Gaussian vector.
Recall that the event $\cE$ is  $u$ satisfies:

* $\|u\|_2\; \ge \frac{1}{2}\sqrt{\frac{2}{3}\din} $    and

* $\forall t\in [N]:P_u^t\le \frac{(7\log(N))^4}{\din^4 \dout}$

where $P_u^t$ is defined as

\begin{align*}
P_u^t%&= \sum_{i,j} \frac{\lambda_{i}\lambda_{j}}{D^2\dout^2\din^4}\left(  \frac{|\bra{u}X_i^\dagger  X_j   \ket{u}|^4}{\|X_i\|_2^2 \|X_j\|_2^2} \right)
&=\sum_{i_t,j_t}\frac{\lambda^t_{i_t}\lambda^t_{j_t}}{D^2\dout^2\din^4}\left(\frac{|\bra{u}A_t^\dagger B_{i_t}^t  B_{j_t}^{t,\dagger}A_t  \ket{u}|^4}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\tr(B_{j_t}^{t,\dagger}A_tA_t^\dagger B_{j_t}^{t})} \right)=\sum_{i,j} \frac{\lambda_{i}\lambda_{j}}{D^2\dout^2\din^4}\left(  \frac{|\bra{u}X_i^\dagger  X_j   \ket{u}|^4}{\|X_i\|_2^2 \|X_j\|_2^2} \right)
\end{align*}

First note that  with high probability $\|u\|_2\ge  \frac{1}{2}\sqrt{\frac{2}{3}\din}$. Indeed, the function $u\mapsto \|u\|_2$ is Lipschitz so $\pr{ \|u\|_2\le \ex{\|u\|_2} -s }\le e^{-s^2/2}$ <cit.>. On the other hand we have by Hölder's inequality $\ex{\|u\|_2}\ge \sqrt{\frac{\ex{\|u\|_2^2}^3}{\ex{\|u\|_2^4}}}=  \sqrt{\frac{\din^3}{\din^2+2\din}}\ge \sqrt{\frac{2}{3}\din }  $ hence

\begin{align*}
\pr{\|u\|_2\le\frac{1}{2}\sqrt{\frac{2}{3}\din} }\le   \pr{\|u\|_2-\ex{\|u\|_2}\le- \frac{1}{2}\sqrt{\frac{2}{3}\din} } \le e^{-\din/32}.
\end{align*}

For the second point in the event $\cE$, we can see that $P_u$ is a  Gaussian polynomial in the entries of $u$  of degree $8$. So we can use the concentration inequality of Gaussian polynomials <cit.>, for any $s>(2e)^{1/4}$ we have:

\begin{align*}
\pr{|P-\ex{P}| \ge s \sqrt{\var(P)}} \le \exp\left(-\frac{4}{e} s^{1/4} \right)
\end{align*}

so with probability at least $1-\frac{1}{N^2}$ we have:

\begin{align*}
P&\le \ex{P} + (e\log(N)/2)^4 \sqrt{\var(P)}
\le  5\log^4(N) \sqrt{\ex{P^2}}.
\end{align*}

Let us control the expectation of $P^2=P_u^2$, recall that we denote $(i,j)=(i_t,j_t)$ and $X_i= B^\dagger_i A_t$,

\begin{align*}
&\ex{P^2} = \mathds{E}\Bigg[ \Bigg(\sum_{i,j} \frac{\lambda_{i}\lambda_{j}}{D^2\dout^2\din^4}\left( \|X_i\|_2^{-2} \|X_j\|_2^{-2}|\bra{u}X_i^\dagger  X_j   \ket{u}|^4 \right)\Bigg)^2\Bigg]
\\&= \mathds{E}\Bigg[ \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\left( \|X_i\|_2^{-2} \|X_j\|_2^{-2}\|X_k\|_2^{-2} \|X_l\|_2^{-2} |\bra{w}X_i^\dagger  X_j   \ket{w}|^4|\bra{w}X_k^\dagger  X_l   \ket{w}|^4 \right)\Bigg] \ex{\|u\|_2^{16}}
% \\&= \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4}\left( \|X_i\|_2^{-2} \|X_j\|_2^{-2}\|X_k\|_2^{-2} \|X_l\|_2^{-2} \mathds{E}\Big[ |\bra{u}X_i^\dagger  X_j   \ket{u}|^2|\bra{u}X_k^\dagger  X_l   \ket{u}|^2\Big]^2 \right)
\\&\le  \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot\frac{ \sum_{\alpha\in \fS_8} \tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k, X_k^\dagger  X_l, X_l^\dagger X_k)}{(\din+7)![(\din-1)!]^{-1}\|X_i\|_2^{2} \|X_j\|_2^{2}\|X_k\|_2^{2} \|X_l\|_2^{2}}\cdot\din^8
\\&\le \max_{\alpha\in \fS_8} \sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot\frac{  |\tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k, X_k^\dagger  X_l, X_l^\dagger X_k)|}{\|X_i\|_2^{2} \|X_j\|_2^{2}\|X_k\|_2^{2} \|X_l\|_2^{2}}
%  \\&\le  \sup_{\beta\in \fS_4}\sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot  \tr_\beta( X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k) ~~~~\text{--need a justification, CS?}
%% \\&\le \sum_{i,j,k,l} \frac{24 \lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\left( \frac{ \sum_{\alpha\in \fS_4} |\tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k)|^2}{\|X_i\|_2^2 \|X_j\|_2^2\|X_k\|_2^2 \|X_l\|_2^2} \right)
%% \\&\le \sum_{i,j,k,l} \frac{24 \lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\left(  \sum_{\alpha\in \fS_4} |\tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k)|  \right)   \textit{ add a proof, CS? }
\end{align*}

Then we claim that:

Let $A= X_i^\dagger  X_j$ and $B= X_k^\dagger  X_l$, we have for all $\alpha\in \fS_8$,

\begin{align*}
&|\tr_\alpha(A,A^\dagger,A,A^\dagger, B, B^\dagger, B, B^\dagger)|^{1/2} %, |\tr_\beta(A,A^\dagger, B, B^\dagger)|
%  \\&\le \max\big\{|\tr(A)|^2|\tr(B)|^2, \tr(AA^\dagger )\tr(BB^\dagger), |\tr(A)|^2 \tr(BB^\dagger),  |\tr(B)|^2 \tr(AA^\dagger) \big\}
\\&\le \max\{ |\tr(A)|^4, \tr(AA^\dagger)^2\}  \max\{ |\tr(B)|^4, \tr(BB^\dagger)^2   \}
\\&\le \|X_i\|_2^{2} \|X_j\|_2^{2}\|X_k\|_2^{2} \|X_l\|_2^{2}.
\end{align*}

Sketch of the proof.
The strategy to prove this lemma depends on $\alpha$, we can give an outline:

* Traces containing one element remain unchanged.

* If we have two successive $A$ (or $B$) in a trace term,  we  upper bound this trace with a $2$-norm $\tr(AA^\dagger)$ times the operator norm of the remaining elements. Then we can upper bound the operator norms with the $2$-norms.

* Otherwise, we have successive $(A,B)$ (with possible adjoint) inside the trace term. We can apply a Cauchy Schwarz inequality then we find two successive $A$ or $B$ and apply the previous strategy.

For instance we have for $\alpha=(1)(5372648)$:

\begin{align*}
\tr(A)\tr(BABA^\dagger B^\dagger A^\dagger B^\dagger )&\le |\tr(A)| \tr(BB^\dagger) \| ABA^\dagger B^\dagger A^\dagger \|_\infty
\\&\le  |\tr(A)| \tr(BB^\dagger) \|BB^\dagger \|_\infty\|AA^\dagger\|^{3/2}_\infty
\\&\le  |\tr(A)| \tr(BB^\dagger) \tr(BB^\dagger )\tr(AA^\dagger)^{3/2}
% \\&\le  |\tr(A)| \tr(BB^\dagger)^2 \tr(AA^\dagger)^{3/2}
% \\&\le \frac{|\tr(A)|^2 \tr(AA^\dagger) \tr(BB^\dagger)^2 }{2}+\frac{ \tr(AA^\dagger)^2 \tr(BB^\dagger)^2 }{2}
% \\&\le \frac{|\tr(A)|^4 \tr(BB^\dagger)^2 }{4}+\frac{\tr(AA^\dagger)^2 \tr(BB^\dagger)^2 }{4}
%  +\frac{ \tr(AA^\dagger)^2 \tr(BB^\dagger)^2 }{2}
\\&\le \max\{ |\tr(A)|^4, \tr(AA^\dagger)^2\}  \max\{ |\tr(B)|^4, \tr(BB^\dagger)^2   \}.
\end{align*}

Another example for $\alpha=(15372648)$:

\begin{align*}
\tr(ABABA^\dagger B^\dagger A^\dagger B^\dagger) &\le \tr(ABABB^\dagger A^\dagger B^\dagger A^\dagger )^{1/2}\tr(BABA A^\dagger B^\dagger A^\dagger B^\dagger )^{1/2}
\\&\le \tr(BB^\dagger) \|AA^\dagger\|^2_\infty \|BB^\dagger\|_\infty
\le \tr(BB^\dagger)^2 \tr(AA^\dagger)^2.
\end{align*}

Using Lemma <ref>, we have:

\begin{align*}
&\ex{P^2} \le \max_{\alpha\in \fS_8} \sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot\frac{  |\tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k, X_k^\dagger  X_l, X_l^\dagger X_k)|}{\|X_i\|_2^{2} \|X_j\|_2^{2}\|X_k\|_2^{2} \|X_l\|_2^{2}}
\\&\le  \max_{\alpha\in \fS_8} \sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \sqrt{|\tr_\alpha(X_i^\dagger  X_j, X_j^\dagger X_i, X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k, X_k^\dagger  X_l, X_l^\dagger X_k)|}
\\&\le  \sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \max\{ |\tr(X_i^\dagger X_j)|^2, \tr(X_i^\dagger X_j X_j^\dagger X_i)\}  \max\{ |\tr(X_k^\dagger X_l)|^2, \tr(X_k^\dagger X_lX_l^\dagger X_k) \}
\end{align*}

So we have $4$ cases to consider, two of them are similar. Let us define four subsets of indices:

\begin{align*}
C_1&=\{(i,j,k,l): |\tr(X_i^\dagger X_j)|^2>\tr(X_i^\dagger X_j X_j^\dagger X_i), |\tr(X_k^\dagger X_l)|^2>\tr(X_k^\dagger X_lX_l^\dagger X_k)\}, \\
C_2&=\{(i,j,k,l):|\tr(X_i^\dagger X_j)|^2\le \tr(X_i^\dagger X_j X_j^\dagger X_i), |\tr(X_k^\dagger X_l)|^2\le \tr(X_k^\dagger X_lX_l^\dagger X_k)\},\\
C_3&=\{(i,j,k,l):|\tr(X_i^\dagger X_j)|^2> \tr(X_i^\dagger X_j X_j^\dagger X_i), |\tr(X_k^\dagger X_l)|^2\le\tr(X_k^\dagger X_lX_l^\dagger X_k)\}, \\
C_4&=\{(i,j,k,l):|\tr(X_i^\dagger X_j)|^2\le \tr(X_i^\dagger X_j X_j^\dagger X_i), |\tr(X_k^\dagger X_l)|^2>\tr(X_k^\dagger X_lX_l^\dagger X_k)\}.
\end{align*}

For the first case where the indices $(i,j,k,l)\in C_1$, we have:

\begin{align*}
&\sum_{i,j,k,l\in C_1}  \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \max\{ |\tr(X_i^\dagger X_j)|^2, \tr(X_i^\dagger X_j X_j^\dagger X_i)\}  \max\{ |\tr(X_k^\dagger X_l)|^2, \tr(X_k^\dagger X_lX_l^\dagger X_k) \}
\\&\le\sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot |\tr (X_i^\dagger  X_j)|^2\tr( X_k^\dagger  X_l)|^2
\\&=\sum_{i,j,k,l}\sum_{x,y,x',y'} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \bra{x}X_i^\dagger  X_j\ket{x}\bra{y}X_j^\dagger  X_i\ket{y}   \bra{x'}X_k^\dagger  X_l\ket{x'}\bra{y'}X_l^\dagger  X_k\ket{y'}
\\&= \sum_{x,y,x',y'} \frac{8!}{D^4\dout^4\din^8} \cdot \dout^4\tr[\tr(A_t\ket{x}\bra{y} A_t^\dagger)\dI_{\dout} \tr(A_t\ket{y}\bra{x} A_t^\dagger)\dI_{\dout} ]
\\&\qquad\qquad\qquad\qquad\qquad\quad \cdot \tr[\tr(A_t\ket{x'}\bra{y'} A_t^\dagger)\dI_{\dout} \tr(A_t\ket{y'}\bra{x'} A_t^\dagger)\dI_{\dout} ]
\\&= \sum_{x,y,x',y'} \frac{8!}{D^4\dout^4\din^8}\cdot \dout^6 \bra{y} A_t^\dagger A_t \ket{x}\bra{x} A_t^\dagger A_t \ket{y} \bra{y'} A_t^\dagger A_t \ket{x'}\bra{x'} A_t^\dagger A_t \ket{y'}
\\&= \frac{8!}{D^4\dout^4\din^8}\cdot \dout^6  \tr( A_t^\dagger A_t A_t^\dagger A_t)^2
\le \frac{8!}{D^4\dout^4\din^8}\cdot \dout^6  \tr( A_t^\dagger A_t )^4
\\& =  \frac{8!}{D^4\dout^4\din^8}\cdot \dout^6 \din^4= \frac{8!}{\din^8\dout^2}
\end{align*}

because $\sum_{i} \lambda_i X_i M X_i^\dagger = \sum_{i} \lambda_i B_i^\dagger A_t M A_t^\dagger B_i= \dout\tr(A_t MA_t^\dagger )\dI_{\dout}$ and $\tr(A_tA_t^\dagger )=\din$.

For the second case where the indices $(i,j,k,l)\in C_2$, we have:

\begin{align*}
&\sum_{i,j,k,l\in C_2}  \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \max\{ |\tr(X_i^\dagger X_j)|^2, \tr(X_i^\dagger X_j X_j^\dagger X_i)\}  \max\{ |\tr(X_k^\dagger X_l)|^2, \tr(X_k^\dagger X_lX_l^\dagger X_k) \}
%  &\sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \tr_\beta( X_i^\dagger  X_j, X_j^\dagger X_i, X_k^\dagger  X_l, X_l^\dagger X_k)
\\&\le \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot\tr(X_i^\dagger  X_j X_j^\dagger X_i)\tr( X_k^\dagger  X_l X_l^\dagger X_k)
% \\&= \sum_{i,j,k,l} \frac{24 \lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4}\left(  \sum_{x,y} \bra{x}X_i^\dagger  X_j\ket{x}\bra{y}X_j^\dagger  X_i\ket{y} \tr( X_k^\dagger  X_l X_l^\dagger X_k)\right)
\\&= \frac{8!}{D^4\dout^4\din^8} \tr(A_tA_t^\dagger ) ^2 \tr(\dI) \tr(A_tA_t^\dagger ) ^2 \tr(\dI) \dout^4
\\& = \frac{8!}{D^4\dout^4\din^8}  \din^4 \dout^6= \frac{8!}{\din^8\dout^2}.
\end{align*}

For the third case where the indices $(i,j,k,l)\in C_3$, we have:

\begin{align*}
&\sum_{i,j,k,l\in C_3}  \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \max\{ |\tr(X_i^\dagger X_j)|^2, \tr(X_i^\dagger X_j X_j^\dagger X_i)\}  \max\{ |\tr(X_k^\dagger X_l)|^2, \tr(X_k^\dagger X_lX_l^\dagger X_k) \}
\\&\le  \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot|\tr(X_i^\dagger  X_j)|^2\tr( X_k^\dagger  X_l X_l^\dagger X_k)
\\&= \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \sum_{x,y}\bra{x}X_i^\dagger  X_j\ket{x}\bra{y}X_j^\dagger  X_i\ket{y}\tr( X_k^\dagger  X_l X_l^\dagger X_k)
\\&= \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \sum_{x,y} \dout^3\bra{y}A_t^\dagger A_t\ket{x} \bra{x}A_t^\dagger A_t\ket{y}  \dout^2 \tr(A_tA_t^\dagger)^2 \tr(\dI)
\\&\le  \sum_{i,j,k,l} \frac{\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot  \dout^6 \tr(A_tA_t^\dagger)^4
% \\&= \sum_{i,j,k,l} \frac{24 \lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4}\left(  \sum_{x,y} \bra{x}X_i^\dagger  X_j\ket{x}\bra{y}X_j^\dagger  X_i\ket{y} \tr( X_k^\dagger  X_l X_l^\dagger X_k)\right)
= \frac{8!}{D^4\dout^4\din^8} \dout^6\din^4
= \frac{8!}{\din^8\dout^2}.
\end{align*}

The fourth case, where the indices $(i,j,k,l)\in C_4$, is similar to the previous one.

To sum up, we have

\begin{align*}
\ex{P^2}
&\le  \sum_{i,j,k,l} \frac{8!\lambda_{i}\lambda_{j}\lambda_k\lambda_l}{D^4\dout^4\din^8}\cdot \max\{ |\tr(X_i^\dagger X_j)|^2, \tr(X_i^\dagger X_j X_j^\dagger X_i)\}  \max\{ |\tr(X_k^\dagger X_l)|^2, \tr(X_k^\dagger X_lX_l^\dagger X_k) \}
\\&\le \frac{4\times 8!}{\din^8\dout^2}.
\end{align*}

So by the union bound, we have with probability at least $1-\frac{1}{N}- e^{-\din/32}\ge \frac{9}{10}$, for all $t\in [N]$:

\begin{align*}
P_u\le 5\log^4(N)^4 \sqrt{\ex{P_u^2}} \le 5\log^4(N) \sqrt{\frac{4\times 8!}{\din^8\dout^2}}\le \frac{(7\log(N))^4 }{\din^4\dout}
\end{align*}

and $\|u\|_2\ge \sqrt{\din/6}$, that is the event $\cE$ is satisfied.

§.§ Proof of Thm. <ref>

Any incoherent ancilla-assisted adaptive algorithm for testing identity to the depolarizing channel requires, in the worst case,

\begin{align*}
N=\Omega\left(\frac{\din^2\dout+ \dout^{1.5}}{\eps^2}\right)
\end{align*}

We use the same construction as in the proof of Thm. <ref>.  Mainly, under the null hypothesis $H_0$ the quantum channel is $\cN(\rho)=\cD(\rho)= \tr(\rho)\frac{\dI}{\dout}$. Under the alternate hypothesis $H_1$, a quantum channel $\cN\sim \cP$ has the form:

\begin{align*}
\cN(\rho)= \tr(\rho) \frac{\dI}{\dout} +\frac{\eps}{\dout} \bra{w}\rho \ket{w} U
\end{align*}

where $\ket{w}= W\ket{0}$ and $W \sim \Haar(\din)$ and for all $i,j\in [\dout]$,  $U_{j,i}=U_{i,j} \sim \mathbf{1}\{i\neq j\}  \cN_c\left(0, \sigma^2=\frac{16}{\dout}\right)$ and we condition on the event $\cG=\{\|U\|_1\ge \dout, \|U\|_\infty \le 32\}$. We call this distribution $\cP$ and use the notation $(w,U)\sim \cP$. Recall that $\pr{\cG}\ge 1-\exp(-\Omega(\dout))-\exp(-\Omega(\dout^2))$ and under $\cG$, the map $\cN$ is a valid quantum channel $\eps$-far from the quantum channel $\cD$.

Now, given a set of observations $i_{<t}=(i_1,\dots, i_{t-1})$. The adaptive algorithm $\cA$ would choose at step $t$ the input $\rho_t^{i_{<t}}$ and the measurement device $\cM_t^{i_{<t}}=\left\{\lambda_{i_t}^{t, i_{<t} } \proj{\phi_{i_t}^{t, i_{<t}}}\right\}_{i_t\in \cI_t}$.

Under the null hypothesis $H_0$, the quantum channel $\cN=\cD$ so the probability of the outcomes is exactly:

\begin{align*}
\mathds{P}_{H_0}^{I_1,\dots, I_N}= \left\{\prod_{t=1}^N\lambda_{i_t}^{t, i_{<t} } \bra{\phi_{i_t}^{t, i_{<t}}}\id\otimes \cD (\rho_t^{i_{<t}}) \ket{\phi_{i_t}^{t, i_{<t}}}\right\}_{i_1,\dots, i_N} .
\end{align*}

On the other hand, under the alternate hypothesis $H_1$, the probability of the outcomes is exactly:

\begin{align*}
\mathds{P}_{H_1, (w,U)}^{I_1,\dots, I_N}= \left\{\prod_{t=1}^N\lambda_{i_t}^{t, i_{<t} } \bra{\phi_{i_t}^{t, i_{<t}}}\id\otimes \cN_{(w,U)} (\rho_t^{i_{<t}}) \ket{\phi_{i_t}^{t, i_{<t}}}\right\}_{i_1,\dots, i_N}
%\left\{\mathds{E}_{(w,U)\sim\cP}\prod_{t=1}^N \frac{\lambda_{i_t}^t}{\dout^N}\left(1+\eps \bra{w}\rho_t\ket{w} \bra{\phi_{i_t}^t}U\ket{\phi_{i_t}^t}  \right) \right\}_{i_1,\dots, i_N}
\end{align*}

Recall that

\begin{align*}
\cJ_\cD= \frac{\dI}{D} ~~\text{ and }~~\cJ_\cN= \frac{\dI}{D}+ \frac{\eps}{D}  \proj{w} \otimes U.
\end{align*}

We can suppose w.l.o.g. that each input state is pure because of the convexity of the $\KL$ divergence. For $t\in [N]$ and ${i_{<t}}$, let $\rho_t^{i_{<t}}= \proj{\psi_t^{i_{<t}}}$. Moreover, we can write each rank one input state and measurement vector as follows:

\begin{align*}
\ket{\psi_t^{i_{<t}}}= A_t^{i_{<t}}\otimes \dI \ket{\Psi_{\din}} ~~\text{ and }~~\ket{\phi_{i_t}^{t, i_{<t}}}=  B_{i_t}^{i_{<t}}\otimes \dI \ket{\Psi_{\dout}}
\end{align*}

where $\ket{\Psi_d}= \frac{1}{\sqrt{d} } \sum_{i=1}^{d} \ket{ii}$ and the matrices $A_t^{i_{<t}} \in \dC^{\danc \times \din }$ and $B_{i_t}^{i_{<t}} \in \dC^{\danc \times \dout }$ verify:

\begin{align*}
\tr(A_t^{i_{<t}}A_t{i_{<t}, \dagger} )= \din  ~~\text{ and }~~  \tr(B_{i_t}^{i_{<t}} B_{i_t}{i_{<t}, \dagger} )= \dout.
\end{align*}

Note that we have for all $t$, $\sum_{i_t} \lambda_{i_t}^{t, i_{<t} }B_{i_t}^{i_{<t}, \dagger}XB_{i_t}^{i_{<t}} = \dout\tr(X)\dI$. Indeed, the condition of the POVM $\cM_t$ implies:

\begin{align*}
X\otimes \dI=    X\otimes \dI\sum_{i_t}\lambda_{i_t}^t \proj{\phi_{i_t}^t} =  \sum_{i_t}\lambda_{i_t}^t XB_{i_t}^t\otimes \dI \proj{\Psi_{\dout}} B_{i_t}^{t, \dagger}\otimes\dI
\end{align*}

hence by taking the partial trace

\begin{align*}
\tr(X) \dI = \frac{1}{\dout}\sum_{i_t, i, j}\lambda_{i_t}^t \bra{j}  B_{i_t}^{t, \dagger}X B_{i_t}^{t} \ket{i}  \ket{i}\bra{j}.
\end{align*}

\begin{align*}
\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger}XB_{i_t}^{t} = \dout\tr(X)\dI.
\end{align*}

Now we can re-write the  distribution  of the observations under the null hypothesis as:

\begin{align*}
\mathds{P}_{H_0}^{I_1,\dots, I_N}&= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cD (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\cJ_\cD (A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&= \left\{\prod_{t=1}^N\frac{\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t} \otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&= \left\{\prod_{t=1}^N\frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})
\right\}_{i_1,\dots, i_N} ,
\end{align*}

and under the alternate hypothesis as:

\begin{align*}
\mathds{P}_{H_1}^{I_1,\dots, I_N}&= \left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\phi_{i_t}^t}\id\otimes \cN (\rho_t) \ket{\phi_{i_t}^t}\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\cJ_\cN (A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N\lambda_{i_t}^t \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t \otimes \dI)\left(\frac{\dI}{D}+ \frac{\eps}{D}  \proj{w} \otimes U \right)(A_t^\dagger B_{i_t}^{t}\otimes \dI) \ket{\Psi_{\dout}}
\right\}_{i_1,\dots, i_N}
\\&=\left\{\prod_{t=1}^N \left( \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})+ \frac{\eps\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}\right)
\right\}_{i_1,\dots, i_N}
\end{align*}

We can express the $\KL$ divergence as follows:

\begin{align*}
& \KL\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1, (w,U)}^{I_1,\dots, I_N}\right)
\\&=\sum_{i_1,\dots, i_N}\prod_{t=1}^N \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})
\\&\quad\quad\quad\quad\quad\quad \times\log\left(\frac{\prod_{t=1}^N \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}{\prod_{t=1}^N \left( \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})+ \frac{\eps\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}\right)}\right)
\\&=\sum_{t=1}^N  \mathds{E}_{\le N}(-\log)\left(1+\frac{\frac{\eps\lambda_{i_t}^t}{D} \bra{\Psi_{\dout}}(B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t}  \otimes U) \ket{\Psi_{\dout}}}{\frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right)
\\&=\sum_{t=1}^N  \mathds{E}_{\le N}(-\log)\left(1+\eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right)
\end{align*}

where we use the notation $\mathds{E}_{\le N}(X(i_1,\dots, i_N))= \sum_{i_1,\dots, i_N}\left(\prod_{t=1}^N \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\right)X(i_1,\dots, i_N)$.
Using the inequality $(-\log(1+x))\le -x+x^2 $ valid for $x\ge -1/2$ and since for $\eps \le 64$, we have $\eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \ge -1/2$, we can upper bound the previous integrand as follows:

\begin{align*}
&(-\log) \left(1+ \eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)
\\&\le \eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} +\eps^2\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U))^2 }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})^2}.
\end{align*}

Observe that the first term vanishes under the expectation:

\begin{align*}
& \mathds{E}_{\le N} \left(\eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}\right)
\\&=   \mathds{E}_{\le t-1}\sum_{i_t} \frac{\lambda_{i_t}^t}{D\dout} \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})\cdot \eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})}
\\&=   \mathds{E}_{\le t-1}\sum_{i_t} \frac{\lambda_{i_t}^t}{D\dout} \cdot\eps\tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U))
\\&= \mathds{E}_{\le t-1} \frac{\eps}{D} \tr(A_t  \proj{w} A_t^\dagger)\tr(U)=0
\end{align*}

where we used $  \sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger}XB_{i_t}^{t} = \dout\tr(X)\dI.$
For the second term, we will instead upper bound its expectation under $U$. Observe that this term is nonnegative, so we can safely remove the condition on the event $\cG$ and then we compute the expectation under $\Haar$  distributed vector $w$ and Gaussians $\{U_{i,j}\}$.

\begin{align*}
\ex{\eps^2 \frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U))^2 }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})^2}}
&\le \frac{32}{\dout}\eps^2\ex{ \frac{\bra{w}A_t^{ \dagger }B_{i_t}^t B_{i_t}^{t, \dagger}  A_t^{ }\ket{w}^2}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})^2} }
\\&\le \frac{64\eps^2}{\dout \din^2} \cdot \frac{\tr(A_t^{ \dagger }B_{i_t}^{t} B_{i_t}^{t, \dagger}  A_t^{ })^2}{\tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})^2}
= \frac{64\eps^2}{\din^2\dout}.
\end{align*}

\begin{align*}
\mathds{E}_{(w,U)\sim\cP}\KL\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1, (w,U)}^{I_1,\dots, I_N}\right)&\le  \sum_{t=1}^N\mathds{E}_{\le N} \mathds{E}_{(w,U)\sim\cP}(-\log) \left(1+\eps\frac{ \tr((B_{i_t}^{t,\dagger}A_t  \proj{w} A_t^\dagger B_{i_t}^{t} U)) }{ \tr(B_{i_t}^{t,\dagger}A_tA_t^\dagger B_{i_t}^{t})} \right)
\\&\le \sum_{t=1}^N\mathds{E}_{\le N} \frac{64\eps^2}{\din^2\dout}= \frac{64N\eps^2}{\din^2\dout}.
\end{align*}

On the other hand, the Data-Processing inequality applied on the $\KL$ divergence (see Prop. <ref>) writes:

\begin{align*}
\mathds{E}_{(w,U)\sim\cP}  \KL\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1, (w,U)}^{I_1,\dots, I_N}\right)
&\ge \mathds{E}_{(w,U)\sim\cP}\KL(\mathds{P}_{H_0}\left(\cA=0\right)\|\mathds{P}_{H_1, (w,U)}\left(\cA=0\right))
\\&\ge \KL(2/3\|1/3)=\frac{2}{3}\log(2)-\frac{1}{3}\log(2)=\frac{1}{3}\log(2).
\end{align*}

Grouping the lower and upper bounds on the $\KL$ divergence:

\begin{align*}
\frac{128N\eps^2}{\din^2\dout}  \ge \mathds{E}_{(w,U)\sim\cP} \KL\left(\mathds{P}_{H_0}^{I_1,\dots, I_N}\Big\| \mathds{P}_{H_1, (w,U)}^{I_1,\dots, I_N}\right)\ge \frac{1}{3}\log(2)
\end{align*}

which yields the lower bound:

\begin{align*}
\end{align*}

§ TESTING IDENTITY OF QUANTUM STATES

In this section, we show how to reduce testing quantum states to testing discrete distributions. The same result with another proof can be found in [Chen et al., 2022].
For a POVM $\cM$ and a quantum state $\rho$, let  $\rho(\cM)$ denotes the classical probability distribution $\{\tr(\rho M_i)\}_{i}$.
The following lemma captures the main ingredient of the reduction:

For all $\delta>0$, let $l=\frac{1}{4}\log(2/\delta)$ and  $U^1,U^2,\dots,U^l\in \mathbb{C}^{d\times d} $ be $\Haar$ -random unitary matrices of columns $\left\{\ket{U_i^j}\right\}_{1\le i\le d, 1\le j \le l} $, $\cM=\left\{\frac{1}{l}\proj{U_i^j}\right\}_{i,j}$   is a POVM
and for all quantum states $\rho$ and $\sigma$ we have with a probability at least $1-\delta$:

\begin{align*}
\TV(\rho(\cM),\sigma(\cM)) \ge\frac{\|\rho-\dI/d\|_2}{20}.% \ge \frac{\|\rho-\sigma\|_{\tr}}{20\sqrt{r}},
\end{align*}

A similar statement can be found in [Matthews et al., 2009] where the authors
analyze the uniform POVM and a POVM defined by a spherical $4$-designs. However, for our reduction, it is important to minimize the number of outcomes of the POVM.

Let $\xi=\rho -\sigma$, we have $U\ket{e_i}=\ket{U_i}$ and we use  Weingarten Calculus <ref> and <ref> to calculate

\begin{align*}
\mathds{E}\left[\bra{U_i}\xi\ket{U_i}^2\right]&=\mathds{E}\left[\bra{U_i}\xi\ket{U_i}\bra{U_i}\xi\ket{U_i}\right]
\\&=\mathds{E}\left[\tr(\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*)\right]
=\mathds{E}\left[\tr(U^*\xi U\proj{e_i}U^*\xi U\proj{e_i})\right]
\\&=\sum_{\alpha,\beta \in \cS_2}\W(\beta\alpha^{-1},d)\tr_{\beta^{-1}}(\xi,\xi)\tr_{\alpha}(\proj{e_i},\proj{e_i})
\end{align*}

\begin{align*}
\mathds{E}\left[\bra{U_i}\xi\ket{U_i}^4\right]&=\mathds{E}\left[\bra{U_i}\xi\ket{U_i}\bra{U_i}\xi\ket{U_i}\bra{U_i}\xi\ket{U_i}\bra{U_i}\xi\ket{U_i}\right]
\\&=\mathds{E}\left[\tr(\xi\proj{U_i}\xi\proj{U_i}\xi\proj{U_i}\xi\proj{U_i})\right]
\\&=\mathds{E}\left[\tr(\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*)\right]
\\&=\mathds{E}\left[\tr(U^*\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*\xi U\proj{e_i}U^*\xi U\proj{e_i})\right]
\\&=\sum_{\alpha,\beta \in \fS_4}\W(\beta\alpha^{-1},d)\tr_{\beta^{-1}}(\xi,\xi,\xi,\xi)\tr_{\alpha}(\proj{e_i},\proj{e_i},\proj{e_i},\proj{e_i})
\\&=\frac{1}{d(d+1)(d+2)(d+3)}(6\tr(\xi^2)^2+6\tr(\xi^4)) .
\\&\le\frac{c'}{d(d+1)(d+2)(d+3)}\tr(\xi^2)^2 .
\end{align*}

We can now conclude by Hölder's inequality:

\begin{align*}
2\mathds{E}\left[ \TV(\rho(\cM),\sigma(\cM)) \right]&=\sum_{i=1}^d \mathds{E}\left[ |\bra{U_i}\xi\ket{U_i}| \right]
\ge \sum_{i=1}^d  \sqrt{\frac{\left(\mathds{E}\left[\bra{U_i}\xi\ket{U_i}^2\right]\right)^3}{\mathds{E}\left[\bra{U_i}\xi\ket{U_i}^4\right]}}
\\&\ge \sum_{i=1}^d  \sqrt{\frac{(d^{-1}(d+1)^{-1}\tr(\xi^2))^3}{c' d^{-1}(d+1)^{-1}(d+2)^{-1}(d+3)^{-1}\tr(\xi^2)^2}}
\\&\ge \sum_{i=1}^d c \frac{\sqrt{\tr{(\xi ^2)}}}{d}
\ge  c \sqrt{\tr{(\rho -\sigma)^2}}.
%\\&\ge  c \frac{\tr|\rho -\sigma|}{\sqrt{d}}
%\\&\ge  c \frac{\|\rho -\sigma\|_{\tr}}{\sqrt{d}}.
\end{align*}

Let $f(U)=\TV(\rho(\cM),\sigma(\cM))$, we first show that $f$ is Lipschitz by using the triangle and Cauchy Schwarz inequalities:

\begin{align*}
2|f(U)-f(V)|&=\left| \sum_{1\le i\le d, 1\le j\le l} \frac{1}{l}|\tr(\proj{U_i^j}\xi)|-|\tr(\proj{V_i^j}\xi)| \right|
\\&\le  \sum_{1\le i\le d, 1\le j\le l} \frac{1}{l}\left|\tr((\proj{U_i^j}-\proj{V_i^j})\xi)\right|
\\&\le  \sum_{1\le i\le d, 1\le j\le l} \frac{1}{l}\sqrt{\tr(\xi^2)}\sqrt{\tr((\proj{U_i^j}-\proj{V_i^j})^2)}
\\&\le  \sqrt{\frac{d}{l}}\sqrt{\tr(\xi^2)}\sqrt{\sum_{1\le i\le d, 1\le j\le l} \tr((\proj{U_i^j}-\proj{V_i^j})^2)}
\\&\le  \sqrt{\frac{d}{l}}\sqrt{\tr(\xi^2)}\sqrt{\sum_{ 1\le j\le l} \tr((U^j-V^j)^2)}
\\&\le  \sqrt{\frac{d}{l}}\sqrt{\tr(\xi^2)}\|U-V\|_{2,\text{HS}},
\end{align*}

hence $f$ is $L=\sqrt{\frac{d}{2l}}\sqrt{\tr(\xi^2)}$-Lipschitz, therefore by Thm. <ref>:

\begin{align*}
\pr{\left|f(U)-\ex{f(U)}\right|>\frac{c}{2}\sqrt{\tr{(\xi^2)}}} \le e^{-\frac{dc^2\tr(\xi^2)}{48L^2}}=e^{-lc^2/24}=\delta/2,
\end{align*}

for $l=24\log(2/\delta)/c^2$. Finally with high probability (at least $ 1-\delta/2$) we have

\begin{align*}
\TV(\rho(\cM),\sigma(\cM))&\ge \ex{\TV(\rho(\cM),\sigma(\cM))}-|\TV(\rho(\cM),\sigma(\cM))-\ex{\TV(\rho(\cM),\sigma(\cM))}|
\\&\ge c\sqrt{\tr(\xi^2)}-\frac{c}{2}\sqrt{\tr(\xi^2)}
\ge \frac{c}{2}\sqrt{\tr(\xi^2)}.
%\ge \frac{c}{2}\frac{\|\rho-\sigma\|_{\tr}}{\sqrt{r}},
\end{align*}

Let $\eta = \|\rho-\dI/d\|_2$.  Under the alternative hypothesis $H_2$, the $\TV$ distance between $P$ and $U_n$ can be lower bounded by $\TV(P,U_n)\ge \frac{1}{20}\|\rho-\dI/d\|_2$. So Lem. <ref> gives a POVM for which our problem reduces to testing identity: $P=U_n$ vs $\TV(P,U_n)\ge \frac{\eta}{20}$  with high probability, where $n=\frac{1}{4}d\log(2/\delta)$ and $P=\cM(\rho)$.
Therefore we can apply the classical testing uniform result of [Diakonikolas et al., 2017] to obtain a copy complexity:

\begin{align*}
%&\mathcal{O}\left( \frac{n^{1/2}\log(1/\delta)^{1/2}}{(\max\{\eps/\sqrt{d}, \|\rho-\dI/d\|_2\})^2}\wedge\frac{\log(1/\delta)}{(\max\{\eps/\sqrt{d}, \|\rho-\dI/d\|_2\})^2}\right)
\mathcal{O}\left( \frac{\sqrt{d}\log(1/\delta)}{\eta^2}\right).
%\\ &= \cO\left( \frac{d^{3/2} \log(1/\delta)}{\eps^2 } \wedge \frac{rd^{0.5} \log(1/\delta)}{\|\rho-\dI/d\|_{\tr}^2 }\right),
\end{align*}

Testing identity of quantum states  in the $2$-norm with an error probability at most $\delta$.
Sample   $U^1,U^2,\dots,U^l\in \mathbb{C}^{d\times d} $  from  $\Haar(d)$ distribution.
Let  $\left\{\ket{U_i^j}\right\}_{1\le i\le d, 1\le j \le l} $ be the columns of the unitary matrices $U^1,U^2,\dots,U^l$
Measure the quantum state $\rho$ using the POVM $\cM=\left\{\frac{1}{l}\proj{U_i^j}\right\}_{i,j}$ and observe $\mathcal{O}\left( \sqrt{d}\log(1/\delta)/\eta^2\right)$
samples from $\rho(\cM)$.
Test whether $h_0:\rho(\cM)= U_{ld}$ or $h_1:\TV(\rho(\cM), U_{ld})\ge \eta/20$ using the testing identity of discrete distributions of [Diakonikolas et al., 2017], with an error probability $\delta$, and answer accordingly.

§ TECHNICAL LEMMAS

In this section, we group technical lemmas useful for the previous proofs of this article.

§.§ Weingarten Calculus

Since we use generally a uniform POVM, which consists in sampling a $\Haar$ -unitary matrix, we need some facts from Weingarten calculus in order to compute $\Haar$ -unitary integrals.  If $\pi$ a permutation of $[n]$, let $\W(\pi,d)$ denotes the Weingarten function of dimension $d$. The following lemma is crucial for our results.
[Gu, 2013] Let $U$ be a $d\times d$ $\Haar$ -distributed unitary matrix and $\{A_i,B_i\}_i$ a sequence of $d\times d$ complex matrices. We have the following formula

\begin{align*}
&\ex{\tr(UB_1U^*A_1U\dots UB_nU^*A_n)}
\\&=\sum_{\alpha,\beta \in \fS_n}\W(\beta\alpha^{-1},d)\tr_{\beta^{-1}}(B_1,\dots,B_n)\tr_{\alpha\gamma_n}(A_1,\dots,A_n),
\end{align*}
where $\gamma_n=(12\dots n)$ and $\tr_{\sigma}(M_1,\dots,M_n)=\Pi_j \tr(\Pi_{i\in C_j} M_i)$ for $\sigma=\Pi_j C_j $ and $C_j$ are cycles.

We need also some values of Weingarten function:

* $\W((1),d)=\frac{1}{d}$,

* $\W((12),d)=\frac{-1}{d(d^2-1)}$,

* $\W((1)(2),d)=\frac{1}{d^2-1}$,

* $\W((123),d)=\frac{2}{d(d^2-1)(d^2-4)}$,

* $\W((12)(3),d)=\frac{-1}{(d^2-1)(d^2-4)}$,

* $\W((1)(2)(3),d)=\frac{d^2-2}{d(d^2-1)(d^2-4)}$.

In particular it is  known that the sum of the Weingarten function has a closed expression:

Let $d,k\in \mathbb{N}^*$. We have

\begin{align*}
\sum_{\alpha\in \fS_k} \W(\alpha, d)= \frac{1}{d(d+1)\cdots(d+k-1)}.
\end{align*}

§.§ Concentration inequalities for Haar-random unitary matrices

The following concentration inequality is important for our results.
[Meckes et al., 2013]
Let $M=\bU(d)^k$ endowed by the $L_2$-norm of Hilbert-Schmidt metric. If $F:M\rightarrow \mathbb{R}$ is $L$-Lipschitz, then for any $t>0$

\begin{align*}
\pr{|F(U_1,\dots,U_k)-\ex{F(U_1,\dots,U_k)}|\ge t} \le e^{-dt^2/12L^2},
\end{align*}

where $U_1,\dots,U_k$ are independent $\Haar$-distributed unitary matrices.

§.§ Kullback-Leibler divergence

The Kullback Leibler divergence is defined for two distributions $P$ and $Q$ on $[d]$ as

\begin{align*}
\KL(P\|Q)=\sum_{i=1}^d P_i\log\left(\frac{P_i}{Q_i}\right)\;.
\end{align*}
We denote by $\KL(p\|q)=\KL(\Ber(p)\|\Ber(q))$.

Kullback-Leibler’s divergence is non-negative and satisfies the Data-Processing  property:

Let $P,P',Q$ and $Q'$ distributions on $[d]$, we have

* Non negativity $\KL(P\|Q)\ge0$.

* Data processing Let $X$ a random variable and $g$ a function. Define the random variable $Y=g(X)$,  we have

\begin{align*}
\KL\left(P^X\|Q^X\right)\ge \KL\left(P^Y\|Q^Y\right).
\end{align*}