Consider the following setting.
I am either given the density matrix $|\psi\rangle \langle \psi|^{\otimes k}$ or the density matrix $\frac{\mathbb{I}^{\otimes k}}{2^{nk}}$, where $\mathbb{I}$ is the $2^{n} \times 2^{n}$ identity matrix.
It is known that $$ |\psi\rangle = C|0^{n}\rangle, $$ for some $C$ which is chosen at random from an ensemble that forms a $k$-design. $$ \mathbb{E}[|\psi\rangle\langle\psi|^{\otimes k}] = \frac{1}{|C|}\sum_{C}C ^{\otimes k}|0\rangle\langle 0|C^{\dagger \otimes k} = \int_{C \sim \text{Haar}} C^{\otimes k}|0\rangle\langle0|C^{\dagger \otimes k} dC_1. $$
We could ask: for any choice of $|\psi\rangle \langle \psi|^{\otimes k}$, what is the optimal test that distinguishes between these two density matrices?
Note that there is a simple strategy that distinguishes between these two states with high probability. Trace out $k-2$ copies, and just perform the SWAP test on the first two copies. No matter what $|\psi\rangle$ we are given, since $|\psi\rangle$ is a pure state, our procedure would accept with probability $1$ when we are given (multiple copies of) $|\psi\rangle$, and accept with a low probability when we are given (multiple copies of) the maximally mixed state.
However, according to this paper (Lemma 20), the optimal test, by utilizing the unitary invariance property of $k$ designs, can also be written in a very specific form.
- Perform weak Schur sampling on the state you are given.
- Obtain outcome $\lambda$ (where $\lambda$ is a partition of $k$ --- for example, $(4, 1)$ is a partition of $5$.)
- Accept with probability $\alpha_{\lambda}$ where $$ \alpha_{\lambda} = d_{\lambda} ~s(x_1, x_2, \ldots, x_{2^{n}}), $$
where $s$ is called the Schur polynomial; $x_1, x_2, \ldots, x_{2^{n}}$ are the eigenvalues corresponding to the density matrix of a single copy of the state; and $d_{\lambda}$ is the dimension of the square matrix associated with the partition $\lambda$. Everything is elucidated in the paper.
However, the eigenvalues corresponding to a single copy of a maximally mixed state over $n$ qubits is $\left(\frac{1}{2^{n}}, \frac{1}{2^{n}}, \ldots, \frac{1}{2^{n}} \right)$. Since a $k$-design is also a $1$ design, the eigenvalues for a single copy of the other density matrix is also $\left(\frac{1}{2^{n}}, \frac{1}{2^{n}}, \ldots, \frac{1}{2^{n}} \right)$. So, the probability of distinguishing these two density matrices using the supposedly optimal Schur sampling method is exactly $0$ --- which is clearly worse than the SWAP test.
How can the Schur sampling method still be optimal?
