# Weak Schur sampling and state distinguishability

Consider the task of distinguishing between the following two $$n$$ qubit quantum states.

$$\rho = \frac{\mathbb{I}}{2^{n}}.$$

$$\sigma = \frac{1}{2^{n/2}}\sum_{x \in \{0, 1\}^{n/2}} |x\rangle\langle x| \otimes |x\rangle\langle x|.$$

We can see that even when we are given just one copy of $$\rho$$ or $$\sigma$$, it is easy to distinguish between these two density matrices with high probability. Just separate out the first and last $$n/2$$ qubits, and apply the SWAP test on them.

It is also easy to see that the total variation distance between these two states is high, and that

$$$$d_{\text{TV}}(\sigma,U \rho U^{*})= d_{\text{TV}}(\sigma, \rho),$$$$ for any unitary $$U$$. Hence, this property is unitarily invariant and we can apply Lemma 20 of this paper (https://arxiv.org/abs/1310.2035) to say that without loss of generality, the optimal distinguisher for these two states does weak Schur sampling followed by classical post-processing.

Note that the eigenvalues of $$\rho$$ are all $$\frac{1}{2^{n}}$$ and those of $$\sigma$$ are $$\frac{1}{2^{n/2}}$$ and $$0$$.

However, I am not sure how weak Schur sampling should work here.

Let's say we are given either one copy of $$\rho$$ or $$\sigma$$.

If we start with $$k$$ copies of a state, after weak Schur sampling, according to this paper, what we get is an estimate of the $$k$$ largest eigenvalues of the state we are given, upto a certain additive accuracy (to argue about the accuracy, see Theorem $$1.4$$ of this paper.)

So, for our setting, applying the said Theorem $$1.4$$, when the state given is $$\rho$$, the estimate $$\lambda$$ we get satisfies

$$\frac{1}{2^{n}} -2 \leq \lambda \leq \frac{1}{2^{n}} + 2$$ and when we are given $$\sigma$$, it satisfies $$\frac{1}{2^{n/2}} -2 \leq \lambda \leq \frac{1}{2^{n/2}} + 2$$

With the classical post-processor, how can we expect to distinguish between these two estimates? I could not think of any algorithm.