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
\begin{equation} d_{\text{TV}}(\sigma,U \rho U^{*})= d_{\text{TV}}(\sigma, \rho), \end{equation} 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.
