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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.