# Optimality of the SWAP test versus weak Schur sampling for testing unitarily invariant properties

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.

1. Perform weak Schur sampling on the state you are given.
2. Obtain outcome $$\lambda$$ (where $$\lambda$$ is a partition of $$k$$ --- for example, $$(4, 1)$$ is a partition of $$5$$.)
3. 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?