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*}
\mathbb{E}(P^2) &\le \sum_{i,j,k,l} \frac{8! \lambda_i \lambda_j \lambda_k \lambda_l}{D^4 d_{\text{out}}^4 d_{\text{in}}^8} \cdot \max\{|\operatorname{Tr}(X_i^\dagger X_j)|^2, \operatorname{Tr}(X_i^\dagger X_j X_j^\dagger X_i)\} \max\{|\operatorname{Tr}(X_k^\dagger X_l)|^2, \operatorname{Tr}(X_k^\dagger X_l X_l^\dagger X_k)\} \\
&\le \frac{4 \times 8!}{d_{\text{in}}^8 d_{\text{out}}^2}.
\end{align*}
$$

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

$$
P_u \le 5 \log^4(N)^4 \sqrt{\mathbb{E}(P_u^2)} \le 5 \log^4(N) \sqrt{\frac{4 \times 8!}{d_{\text{in}}^8 d_{\text{out}}^2}} \le \frac{(7 \log(N))^4}{d_{\text{in}}^4 d_{\text{out}}}
$$

and $\|u\|_2 \ge \sqrt{d_{\text{in}}/6}$, that is the event $\mathcal{E}$ is satisfied.

<figure><img src="image_14.png" /></figure>

D.2 Proof of Thm. 4.6

**Theorem D.5.** Any incoherent ancilla-assisted adaptive algorithm for testing identity to the depolarizing channel requires, in the worst case,

$$
N = \Omega \left( \frac{d_{\text{in}}^2 d_{\text{out}} + d_{\text{out}}^{1.5}}{\varepsilon^2} \right)
$$

measurements.

Proof. We use the same construction as in the proof of Thm. 4.5. Mainly, under the null hypothesis $H_0$ the quantum channel is $\mathcal{N}(\rho) = \mathcal{D}(\rho) = \operatorname{Tr}(\rho) \frac{1}{d_{\text{out}}}$.
Under the alternate hypothesis $H_1$, a quantum channel $\mathcal{N} \sim \mathcal{P}$ has the form:

$$
\mathcal{N}(\rho) = \operatorname{Tr}(\rho) \frac{\mathbb{I}}{d_{\text{out}}} + \frac{\varepsilon}{d_{\text{out}}} \langle w | \rho | w \rangle U
$$

where $|w\rangle = W|0\rangle$ and $W \sim \text{Haar}(d_{\text{in}})$ and for all $i, j \in [d_{\text{out}}]$, $U_{j,i} = U_{i,j} \sim \mathbb{1}\{i \neq j\} \mathcal{N}_c(0, \sigma^2 = \frac{16}{d_{\text{out}}})$
and we condition on the event $\mathcal{G} = \{\|U\|_1 \ge d_{\text{out}}, \|U\|_{\infty} \le 32\}$. We call this distribution $\mathcal{P}$ and use the
notation $(w, U) \sim \mathcal{P}$. Recall that $\mathbb{P}(\mathcal{G}) \ge 1 - \exp(-\Omega(d_{\text{out}})) - \exp(-\Omega(d_{\text{out}}^2))$ and under $\mathcal{G}$, the map $\mathcal{N}$
is a valid quantum channel $\varepsilon$-far from the quantum channel $\mathcal{D}$.

Now, given a set of observations $i_{<t} = (i_1, \dots, i_{t-1})$. The adaptive algorithm $\mathcal{A}$ would choose at step $t$
the input $\rho_t^{i<t}$ and the measurement device $\mathcal{M}_t^{i<t} = \left\{ \lambda_{it}^{t,i<t} \middle| \phi_{it}^{t,i<t} \rangle \langle \phi_{it}^{t,i<t} | \right\}_{i_t \in \mathcal{I}_t}$.

Under the null hypothesis $H_0$, the quantum channel $\mathcal{N} = \mathcal{D}$ so the probability of the outcomes is exactly:

$$
\mathbb{P}_{H_0}^{I_1, \dots, I_N} = \left\{ \prod_{t=1}^{N} \lambda_{it}^{t, i<t} \left\langle \phi_{it}^{t, i<t} \middle| \mathrm{id} \otimes \mathcal{D}(\rho_t^{i<t}) \middle| \phi_{it}^{t, i<t} \right\rangle \right\}_{i_1, \dots, i_N} .
$$

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

$$
\mathbb{P}_{H_1(w,U)}^{I_1, \dots, I_N} = \left\{ \prod_{t=1}^{N} \lambda_{it}^{t, i<t} \left\langle \phi_{it}^{t, i<t} \middle| \mathrm{id} \otimes \mathcal{N}_{(w,U)}(\rho_t^{i<t}) \middle| \phi_{it}^{t, i<t} \right\rangle \right\}_{i_1, \dots, i_N}
$$
Recall that

$$ \mathcal{J}_D = \frac{\mathbb{I}}{D} \quad \text{and} \quad \mathcal{J}_N = \frac{\mathbb{I}}{D} + \frac{\varepsilon}{D} |w\rangle\langle w| \otimes U. $$

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} = |\psi_t^{i<t}\rangle\langle\psi_t^{i<t}|$. Moreover, we can write each rank one input state and measurement vector as follows:

$$ |\psi_t^{i<t}\rangle = A_t^{i<t} \otimes \mathbb{I} |\Psi_{d_{\text{in}}}\rangle \quad \text{and} \quad |\phi_{it}^{t,i<t}\rangle = B_{it}^{i<t} \otimes \mathbb{I} |\Psi_{d_{\text{out}}}\rangle $$

where $|\Psi_d\rangle = \frac{1}{\sqrt{d}} \sum_{i=1}^d |ii\rangle$ and the matrices $A_t^{i<t} \in \mathbb{C}^{d_{\text{anc}} \times d_{\text{in}}}$ and $B_{it}^{i<t} \in \mathbb{C}^{d_{\text{anc}} \times d_{\text{out}}}$ verify:

$$ \mathrm{Tr}(A_t^{i<t} A_t i_{<t}, \dagger) = d_{\text{in}} \quad \text{and} \quad \mathrm{Tr}(B_{it}^{i<t} B_{it} i_{<t}, \dagger) = d_{\text{out}}. $$

Note that we have for all $t$, $\sum_{it} \lambda_{it}^{t,i<t} B_{it}^{i<t,\dagger} X B_{it}^{i<t} = d_{\text{out}} \mathrm{Tr}(X) \mathbb{I}$. Indeed, the condition of the POVM $\mathcal{M}_t$ implies:

$$ X \otimes \mathbb{I} = X \otimes \mathbb{I} \sum_{it} \lambda_{it}^{t} |\phi_{it}^{t}\rangle\langle\phi_{it}^{t}| = \sum_{it} \lambda_{it}^{t} X B_{it}^{t} \otimes \mathbb{I} |\Psi_{d_{\text{out}}}\rangle\langle\Psi_{d_{\text{out}}}| B_{it}^{t,\dagger} \otimes \mathbb{I} $$

hence by taking the partial trace

$$ \mathrm{Tr}(X)\mathbb{I} = \frac{1}{d_{\text{out}}} \sum_{it,i,j} \lambda_{it}^{t} \langle j | B_{it}^{t,\dagger} X B_{it}^{t} | i \rangle |i\rangle \langle j|. $$

Finally

$$ \sum_{it} \lambda_{it}^{t} B_{it}^{t,\dagger} X B_{it}^{t} = d_{\text{out}} \mathrm{Tr}(X) \mathbb{I}. $$

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

$$ \begin{aligned} \mathbb{P}_{H_0}^{I_1, \dots, I_N} &= \left\{ \prod_{t=1}^{N} \lambda_{it}^{t} \langle \phi_{it}^{t} | \mathrm{id} \otimes \mathcal{D}(\rho_t) | \phi_{it}^{t} \rangle \right\}_{i_1, \dots, i_N} \\ &= \left\{ \prod_{t=1}^{N} \lambda_{it}^{t} \langle \Psi_{d_{\text{out}}} | (B_{it}^{t,\dagger} A_t \otimes \mathbb{I}) \mathcal{J}_D (A_t^{\dagger} B_{it}^{t} \otimes \mathbb{I}) | \Psi_{d_{\text{out}}} \rangle \right\}_{i_1, \dots, i_N} \\ &= \left\{ \prod_{t=1}^{N} \frac{\lambda_{it}^{t}}{D} \langle \Psi_{d_{\text{out}}} | (B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t} \otimes \mathbb{I}) | \Psi_{d_{\text{out}}} \rangle \right\}_{i_1, \dots, i_N} \\ &= \left\{ \prod_{t=1}^{N} \frac{\lambda_{it}^{t}}{D d_{\text{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t}) \right\}_{i_1, \dots, i_N}, \end{aligned} $$
and under the alternate hypothesis as:

$$
\begin{align*}
\mathbb{P}_{H_1}^{I_1, \dots, I_N} &= \left\{ \prod_{t=1}^{N} \lambda_{it}^{t} \langle \phi_{it}^{t} | \mathrm{id} \otimes \mathcal{N}(\rho_t) | \phi_{it}^{t} \rangle \right\}_{i_1, \dots, i_N} \\
&= \left\{ \prod_{t=1}^{N} \lambda_{it}^{t} \langle \Psi_{d_{\mathrm{out}}} | (B_{it}^{t, \dagger} A_t \otimes \mathbb{I}) \mathcal{J}_{\mathcal{N}}(A_t^{\dagger} B_{it}^{t} \otimes \mathbb{I}) | \Psi_{d_{\mathrm{out}}} \rangle \right\}_{i_1, \dots, i_N} \\
&= \left\{ \prod_{t=1}^{N} \lambda_{it}^{t} \langle \Psi_{d_{\mathrm{out}}} | (B_{it}^{t, \dagger} A_t \otimes \mathbb{I}) \left( \frac{\mathbb{I}}{D} + \frac{\varepsilon}{D} |w\rangle \langle w| \otimes U \right) (A_t^{\dagger} B_{it}^{t} \otimes \mathbb{I}) | \Psi_{d_{\mathrm{out}}} \rangle \right\}_{i_1, \dots, i_N} \\
&= \left\{ \prod_{t=1}^{N} \left( \frac{\lambda_{it}^{t}}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t, \dagger} A_t A_t^{\dagger} B_{it}^{t}) + \frac{\varepsilon \lambda_{it}^{t}}{D} \langle \Psi_{d_{\mathrm{out}}} | (B_{it}^{t, \dagger} A_t |w\rangle \langle w| A_t^{\dagger} B_{it}^{t} \otimes U) | \Psi_{d_{\mathrm{out}}} \rangle \right) \right\}_{i_1, \dots, i_N}
\end{align*}
$$

We can express the KL divergence as follows:

$$
\begin{align*}
\mathrm{KL} \left( \mathbb{P}_{H_0}^{I_1, \dots, I_N} \middle\| \mathbb{P}_{H_1, (w,U)}^{I_1, \dots, I_N} \right) \\
&= \sum_{i_1, \dots, i_N} \prod_{t=1}^{N} \frac{\lambda_{it}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t}) \\
&\quad \times \log \left( \frac{\prod_{t=1}^{N} \frac{\lambda_{it}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})}{\prod_{t=1}^{N} \left( \frac{\lambda_{it}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t}) + \frac{\varepsilon \lambda_{it}^t}{D} \langle \Psi_{d_{\mathrm{out}}} | (B_{it}^{t,\dagger} A_t |w\rangle \langle w| A_t^{\dagger} B_{it}^{t} \otimes U) | \Psi_{d_{\mathrm{out}}} \rangle \right)} \right) \\
&= \sum_{t=1}^{N} \mathrm{E}_{\le N} (-\log) \left( 1 + \frac{\frac{\varepsilon \lambda_{it}^t}{D} \langle \Psi_{d_{\mathrm{out}}} | (B_{it}^{t,\dagger} A_t |w\rangle \langle w| A_t^{\dagger} B_{it}^{t} \otimes U) | \Psi_{d_{\mathrm{out}}} \rangle}{\frac{\lambda_{it}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})} \right) \\
&= \sum_{t=1}^{N} \mathrm{E}_{\le N} (-\log) \left( 1 + \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle \langle w| A_t^{\dagger} B_{it}^{t} U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})} \right)
\end{align*}
$$

where we use the notation $\mathrm{E}_{\le N}(X(i_1, \dots, i_N)) = \sum_{i_1, \dots, i_N} \left( \prod_{t=1}^{N} \frac{\lambda_{it}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{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 $\varepsilon \le 64$, we have

$$
\varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^{t} U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})} \ge -1/2, \text{ we can upper bound the previous integrand as follows:}
$$

$$
(-\log) \left( 1 + \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^{t} U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})} \right) \\
\le \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^{t} U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})} + \varepsilon^2 \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^{t} U))^2}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^{t})^2}.
$$
Observe that the first term vanishes under the expectation:

$$
\begin{align*}
& \mathrm{E}_{\le N} \left( \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^t U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)} \right) \\
&= \mathrm{E}_{\le t-1} \sum_{i_t} \frac{\lambda_{i_t}^t}{D d_{\mathrm{out}}} \mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t) \cdot \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^t U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)} \\
&= \mathrm{E}_{\le t-1} \sum_{i_t} \frac{\lambda_{i_t}^t}{D d_{\mathrm{out}}} \cdot \varepsilon \mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^t U)) \\
&= \mathrm{E}_{\le t-1} \frac{\varepsilon}{D} \mathrm{Tr}(A_t |w\rangle\langle w| A_t^{\dagger}) \mathrm{Tr}(U) = 0
\end{align*}
$$

where we used $\sum_{i_t} \lambda_{i_t}^t B_{i_t}^{t,\dagger} X B_{i_t}^t = d_{\text{out}} \text{Tr}(X)\mathbb{I}$. 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 $\mathcal{G}$ and then we compute the expectation under Haar distributed vector $w$ and Gaussians $\{U_{i,j}\}$.

$$
\begin{align*}
\mathrm{E} \left( \varepsilon^2 \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^t U))^2}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)^2} \right) &\le \frac{32}{d_{\mathrm{out}}} \varepsilon^2 \mathrm{E} \left( \frac{\langle w| A_t^{\dagger} B_{it}^t B_{it}^{t,\dagger} A_t |w\rangle^2}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)^2} \right) \\
&\le \frac{64\varepsilon^2}{d_{\mathrm{out}} d_{\mathrm{in}}^2} \cdot \frac{\mathrm{Tr}(A_t^{\dagger} B_{it}^t B_{it}^{t,\dagger} A_t)^2}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)^2} = \frac{64\varepsilon^2}{d_{\mathrm{in}}^2 d_{\mathrm{out}}}.
\end{align*}
$$

Therefore

$$
\begin{align*}
\mathrm{E}_{(w,U)\sim\mathcal{P}} \mathrm{KL} \left( \mathbb{P}_{H_0}^{I_1, \dots, I_N} \left\| \mathbb{P}_{H_1, (w,U)}^{I_1, \dots, I_N} \right\| \right) &\le \sum_{t=1}^N \mathrm{E}_{\le N} \mathrm{E}_{(w,U)\sim\mathcal{P}} (-\log) \left( 1 + \varepsilon \frac{\mathrm{Tr}((B_{it}^{t,\dagger} A_t |w\rangle\langle w| A_t^{\dagger} B_{it}^t U))}{\mathrm{Tr}(B_{it}^{t,\dagger} A_t A_t^{\dagger} B_{it}^t)} \right) \\
&\le \sum_{t=1}^N \mathrm{E}_{\le N} \frac{64\varepsilon^2}{d_{\mathrm{in}}^2 d_{\mathrm{out}}} = \frac{64N\varepsilon^2}{d_{\mathrm{in}}^2 d_{\mathrm{out}}}.
\end{align*}
$$

On the other hand, the Data-Processing inequality applied on the KL divergence (see Prop. F.3) writes:

$$
\begin{align*}
\mathrm{E}_{(w,U)\sim\mathcal{P}} \mathrm{KL} \left( \mathbb{P}_{H_0}^{I_1, \dots, I_N} \left\| \mathbb{P}_{H_1, (w,U)}^{I_1, \dots, I_N} \right\| \right) &\ge \mathrm{E}_{(w,U)\sim\mathcal{P}} \mathrm{KL}(\mathbb{P}_{H_0} (\mathcal{A}=0) \| \mathbb{P}_{H_1, (w,U)} (\mathcal{A}=0)) \\
&\ge \mathrm{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:

$$
\frac{128N\varepsilon^2}{d_{\text{in}}^2 d_{\text{out}}} \geq \mathrm{E}_{(w,U)\sim\mathcal{P}} \mathrm{KL} \left( \mathbb{P}_{H_0}^{I_1, \dots, I_N} \left\| \mathbb{P}_{H_1, (w,U)}^{I_1, \dots, I_N} \right\| \right) \geq \frac{1}{3} \log(2)
$$

which yields the lower bound:

$$
N = \Omega \left( \frac{d_{\text{in}}^2 d_{\text{out}}}{\varepsilon^2} \right).
$$

<figure><img src="image_15.png" /></figure>
E 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., 2022a]. For a POVM $\mathcal{M}$ and a quantum state $\rho$, let $\rho(\mathcal{M})$ denotes the classical probability distribution $\{\text{Tr}(\rho M_i)\}_i$. The following lemma captures the main ingredient of the reduction:

**Lemma E.1.** 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 $\{|U_i^j\rangle\}_{1 \le i \le d, 1 \le j \le l'}$, $\mathcal{M} = \{\frac{1}{l}|U_i^j\rangle\langle U_i^j|\}_{i,j}$ is a POVM and for all quantum states $\rho$ and $\sigma$ we have with a probability at least $1 - \delta$:

$$ \mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M})) \geq \frac{\|\rho - \mathbb{I}/d\|_2}{20}. $$

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.

*Proof.* Let $\xi = \rho - \sigma$, we have $U |e_i\rangle = |U_i\rangle$ and we use Weingarten Calculus F.1 and F.2 to calculate

$$ \begin{aligned} \mathrm{E} [\langle U_i | \xi | U_i \rangle^2] &= \mathrm{E} [\langle U_i | \xi | U_i \rangle \langle U_i | \xi | U_i \rangle] = \mathrm{E} [\mathrm{Tr}(\xi |U_i\rangle\langle U_i| \xi |U_i\rangle\langle U_i|)] \\ &= \mathrm{E} [\mathrm{Tr}(\xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i| U^*)] = \mathrm{E} [\mathrm{Tr}(U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i|)] \\ &= \sum_{\alpha, \beta \in S_2} \mathrm{Wg}(\beta \alpha^{-1}, d) \mathrm{Tr}_{\beta^{-1}}(\xi, \xi) \mathrm{Tr}_{\alpha}(|e_i\rangle\langle e_i|, |e_i\rangle\langle e_i|) = \frac{1}{d(d+1)} \mathrm{Tr}(\xi^2). \end{aligned} $$

Similarly

$$ \begin{aligned} \mathrm{E} [\langle U_i | \xi | U_i \rangle^4] &= \mathrm{E} [\langle U_i | \xi | U_i \rangle \langle U_i | \xi | U_i \rangle \langle U_i | \xi | U_i \rangle \langle U_i | \xi | U_i \rangle] \\ &= \mathrm{E} [\mathrm{Tr}(\xi |U_i\rangle\langle U_i| \xi |U_i\rangle\langle U_i| \xi |U_i\rangle\langle U_i| \xi |U_i\rangle\langle U_i|)] \\ &= \mathrm{E} [\mathrm{Tr}(\xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i|)] \\ &= \mathrm{E} [\mathrm{Tr}(U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i| U^* \xi U |e_i\rangle\langle e_i|)] \\ &= \sum_{\alpha, \beta \in S_4} \mathrm{Wg}(\beta \alpha^{-1}, d) \mathrm{Tr}_{\beta^{-1}}(\xi, \xi, \xi) \mathrm{Tr}_{\alpha}(|e_i\rangle\langle e_i|, |e_i\rangle\langle e_i|, |e_i\rangle\langle e_i|, |e_i\rangle\langle e_i|) \\ &= \frac{1}{d(d+1)(d+2)(d+3)} (6\mathrm{Tr}(\xi^2)^2 + 6\mathrm{Tr}(\xi^4)). \\ &\le \frac{c'}{d(d+1)(d+2)(d+3)} \mathrm{Tr}(\xi^2)^2. \end{aligned} $$

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

$$ \begin{aligned} 2\mathrm{E}[\mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M}))] &= \sum_{i=1}^{d} \mathrm{E}[|\langle U_i | \xi | U_i \rangle|] \ge \sum_{i=1}^{d} \sqrt{\frac{\left(\mathrm{E}[\langle U_i | \xi | U_i \rangle^2]\right)^3}{\mathrm{E}[\langle U_i | \xi | U_i \rangle^4]}} \\ &\ge \sum_{i=1}^{d} \sqrt{\frac{(d^{-1}(d+1)^{-1}\mathrm{Tr}(\xi^2))^3}{c' d^{-1}(d+1)^{-1}(d+2)^{-1}(d+3)^{-1}\mathrm{Tr}(\xi^2)^2}} \\ &\ge \sum_{i=1}^{d} c \frac{\sqrt{\mathrm{Tr}(\xi^2)}}{d} \ge c \sqrt{\mathrm{Tr}(\rho - \sigma)^2}. \end{aligned} $$
Let $f(U) = \text{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M}))$, 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} |\text{Tr}(|U_i^j\rangle\langle U_i^j| \xi)| - |\text{Tr}(|V_i^j\rangle\langle V_i^j| \xi)| \right| \\
&\le \sum_{1 \le i \le d, 1 \le j \le l} \frac{1}{l} \left| \text{Tr}((|U_i^j\rangle\langle U_i^j| - |V_i^j\rangle\langle V_i^j|)\xi) \right| \\
&\le \sum_{1 \le i \le d, 1 \le j \le l} \frac{1}{l} \sqrt{\text{Tr}(\xi^2)} \sqrt{\text{Tr}((|U_i^j\rangle\langle U_i^j| - |V_i^j\rangle\langle V_i^j|)^2)} \\
&\le \sqrt{\frac{d}{l}} \sqrt{\text{Tr}(\xi^2)} \sqrt{\sum_{1 \le i \le d, 1 \le j \le l} \text{Tr}((|U_i^j\rangle\langle U_i^j| - |V_i^j\rangle\langle V_i^j|)^2)} \\
&\le \sqrt{\frac{d}{l}} \sqrt{\text{Tr}(\xi^2)} \sqrt{\sum_{1 \le j \le l} \text{Tr}((U^j - V^j)^2)} \\
&\le \sqrt{\frac{d}{l}} \sqrt{\text{Tr}(\xi^2)} \|U - V\|_{2,\text{HS}},
\end{align*}
$$

hence $f$ is $L = \sqrt{\frac{d}{2l}}\sqrt{\text{Tr}(\xi^2)}$-Lipschitz, therefore by Thm. F.4:

$$
\mathbb{P} \left( |f(U) - \mathrm{E}(f(U))| > \frac{c}{2} \sqrt{\mathrm{Tr}(\xi^2)} \right) \le e^{-\frac{dc^2 \mathrm{Tr}(\xi^2)}{48L^2}} = e^{-lc^2/24} = \delta/2,
$$

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

$$
\begin{align*}
\mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M})) &\ge \mathrm{E}(\mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M}))) - |\mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M})) - \mathrm{E}(\mathrm{TV}(\rho(\mathcal{M}), \sigma(\mathcal{M})))| \\
&\ge c\sqrt{\mathrm{Tr}(\xi^2)} - \frac{c}{2}\sqrt{\mathrm{Tr}(\xi^2)} \ge \frac{c}{2}\sqrt{\mathrm{Tr}(\xi^2)}.
\end{align*}
$$

<figure><img src="image_16.png" /></figure>

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

$$
\mathcal{O}\left(\frac{\sqrt{d \log(1/\delta)}}{\eta^2}\right).
$$

F Technical lemmas

In this section, we group technical lemmas useful for the previous proofs of this article.
**Algorithm 3:** Testing identity of quantum states in the 2-norm with an error probability at most δ.

$l = \frac{1}{4} \log(2/\delta)$.

Sample $U^1, U^2, \dots, U^l \in \mathbb{C}^{d \times d}$ from Haar($d$) distribution.

Let $\{|U_i^j\rangle\}_{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 $\mathcal{M} = \{\frac{1}{l}|U_i^j\rangle\langle U_i^j|\}_{i,j}$ and observe

$\mathcal{O}(\sqrt{d} \log(1/\delta)/\eta^2)$ samples from $\rho(\mathcal{M})$.

Test whether $h_0 : \rho(\mathcal{M}) = U_{ld}$ or $h_1 : \text{TV}(\rho(\mathcal{M}), 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.

## F.1 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 $\text{Wg}(\pi, d)$ denotes the Weingarten function of dimension $d$. The following lemma is crucial for our results.

**Lemma F.1.** [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{aligned} & \mathrm{E} (\mathrm{Tr}(UB_1U^*A_1U \dots UB_nU^*A_n)) \\ & = \sum_{\alpha, \beta \in \mathfrak{S}_n} \mathrm{Wg}(\beta\alpha^{-1}, d) \mathrm{Tr}_{\beta^{-1}}(B_1, \dots, B_n) \mathrm{Tr}_{\alpha\gamma_n}(A_1, \dots, A_n), \end{aligned} $$

where $\gamma_n = (12 \dots n)$ and $\mathrm{Tr}_\sigma(M_1, \dots, M_n) = \prod_j \mathrm{Tr}(\prod_{i \in C_j} M_i)$ for $\sigma = \prod_j C_j$ and $C_j$ are cycles.

We need also some values of Weingarten function:

**Lemma F.2.** • $\text{Wg}((1), d) = \frac{1}{d}$,

• $\text{Wg}((12), d) = \frac{-1}{d(d^2-1)}$,

• $\text{Wg}((1)(2), d) = \frac{1}{d^2-1}$,

• $\text{Wg}((123), d) = \frac{2}{d(d^2-1)(d^2-4)}$,

• $\text{Wg}((12)(3), d) = \frac{-1}{(d^2-1)(d^2-4)}$,

• $\text{Wg}((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:

**Lemma F.3.** [Collins et al., 2012] Let $d, k \in \mathbb{N}^*$. We have

$$ \sum_{\alpha \in \mathfrak{S}_k} \mathrm{Wg}(\alpha, d) = \frac{1}{d(d+1)\cdots(d+k-1)}. $$
## F.2 Concentration inequalities for Haar-random unitary matrices

The following concentration inequality is important for our results.

**Theorem F.4.** [Meckes et al., 2013] Let $M = \mathbb{U}(d)^k$ endowed by the $L_2$-norm of Hilbert-Schmidt metric. If $F: M \to \mathbb{R}$ is L-Lipschitz, then for any $t > 0$

$$ \mathbb{P}(|F(U_1, \dots, U_k) - \mathbb{E}(F(U_1, \dots, U_k))| \ge t) \le e^{-dt^2/12L^2}, $$

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

## F.3 Kullback-Leibler divergence

**Definition F.5 (Kullback Leibler divergence).** The Kullback Leibler divergence is defined for two distributions $P$ and $Q$ on $[d]$ as

$$ \mathrm{KL}(P\|Q) = \sum_{i=1}^{d} P_i \log \left( \frac{P_i}{Q_i} \right). $$

We denote by $\mathrm{KL}(p\|q) = \mathrm{KL}(\mathrm{Bern}(p)\|\mathrm{Bern}(q))$.

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

**Proposition F.6 ([Van Erven and Harremos, 2014]).** Let $P, P', Q$ and $Q'$ distributions on $[d]$, we have

* **Non negativity** $\mathrm{KL}(P\|Q) \ge 0$.

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

$$ \mathrm{KL}(P^X\|Q^X) \ge \mathrm{KL}(P^Y\|Q^Y). $$