# Is it possible to distinguish a pure state from a "partially uniform" state?

Let $$f$$ be a random function mapping $$n$$ bits to $$m$$ bits. Let $$|\phi\rangle$$ be a state that is whether (1) $$\sum_x2^{-n/2}|x,f(x)\rangle$$ or (2) a pure state $$|x,f(x)\rangle$$ for some random and unknown $$x$$. Is it possible to distinguish the two?

• Do you know the function $f$? If so, you have the chance to uncompute f, so that you're just trying to distinguish between $|+\rangle^{\otimes n}$ and $|x\rangle$. While you can't do that perfectly, you can do it with extremely high probability by measuring every qubit in the $X$ basis. Jul 21, 2023 at 8:08
• Do you have a single copy or multiple copies? Jul 21, 2023 at 8:08

As mentioned by @DaftWullie, if you know $$f$$ then you can uncompute it and end up with $$\frac{1}{2^n}\sum_x|x,0\rangle$$ vs. $$|x, 0\rangle$$. You can then apply an $$H$$ gate on the first register, which gives you $$|0,0\rangle$$ vs. $$\frac{1}{\sqrt{2^n}}\sum_{y}(-1)^{x\cdot y}|y, 0\rangle$$. Thus measuring the first register gives you $$|0\rangle$$ with probability $$1$$ in the first case and with probability $$\frac{1}{2^n}$$ in the second case.

As mentioned by @Rammus, if you have multiple copies and assumming the random $$x$$ is always the same, you can simply measure the first register on all copies. With $$t$$ copies, you have a very high probability of measuring two different states in the first case, but not in the second one.

If you have multiple copies but the random $$x$$ is independently chosen each time, then two copies are enough to distinguish them via a SWAP test, which will work with probability $$\approx\frac34$$. This gets exponentially better with more copies.

Finally, in case you have a single copy and you don't know $$f$$, then you can't with overwhelming probability. The density matrix for the second case is the maximally mixed one $$\sigma=\frac{1}{2^{n+m}}I_{2^{n+m}}$$. For the first case, it is: $$\rho=\frac{1}{2^n2^{m2^n}}\sum_{x,y}\sum_f|x, f(x)\rangle\!\langle y, f(y)|.$$ We are interested in the coefficient of $$|x, a\rangle\!\langle y, b|$$, so we compute: $$\langle x, a|\rho|y, b\rangle=\frac{1}{2^n2^{m2^n}}\sum_{x,y}\sum_{\substack{f\\f(x)=a\\f(y)=b}}|x, a\rangle\!\langle y, b|.$$ If $$x=y$$, then this forces $$a=b$$, which represents a diagonal coefficient. The number of functions from $$\{0, 1\}^n$$ to $$\{0, 1\}^m$$ with a fixed input is $$2^{m\left(2^n-1\right)}$$. Thus the value of this coefficient is $$\frac{1}{2^{n+m}}$$. If $$x\neq y$$, there is no relation between $$a$$ and $$b$$, so this represent every off-diagonal component. A similar computation tells you that their value is $$\frac{1}{2^{n+2m}}$$. Thus, we have: $$\rho-\sigma=\frac{1}{2^{n+2m}}\begin{pmatrix}0&1&1&\cdots&1\\1 & 0 & 1 & \cdots& 1\\1&1&0&\cdots & 1\\\vdots & \vdots & \ddots & \vdots & \vdots\end{pmatrix}.$$ In order to compute the trace distance between $$\rho$$ and $$\sigma$$, we are interested in the eigenvalues of this matrix. Fortunately, this is a well-known matrix.

The $$N\times N$$ all $$1$$ matrix has rank $$1$$. Thus, its kernel has dimension $$N-1$$. Let us consider a vector $$u$$ of this kernel. We have $$(1-I)u=-u$$, thus $$-1$$ is an eigenvalue of $$1-I$$ with multiplicity $$N-1$$. We're just missing the final eigenvalue, which can be found using the fact that the trace of $$1-I$$ is nil. Thus, the final eigenvalue is $$N-1$$.

All in all, the trace distance between $$\rho$$ and $$\sigma$$ is equal to $$\frac{1}{2^{n+2m}}\left(\frac{2^{n+m}-1}{2}+\frac{2^{n+m}-1}{2}\right)=\frac{1}{2^{m}}-\frac{1}{2^{n+2m}}.$$ This means that the maximum probability with which you can distinguish $$\rho$$ and $$\sigma$$ is $$\frac12+\frac{1}{2^{m+1}}-\frac{1}{2^{n+2m+1}}$$. Thus, there is no efficient algorithm to do so in the single-copy, unknown function case.

• Why are you summing the eigenvalues? You should sum their absolute values to get the trace norm, and the result is $2^{-m}-2^{-n-2m}$. Jul 21, 2023 at 12:36
• @MateusAraújo Oops, you're right! Jul 21, 2023 at 15:02
• Thanks for the brilliant answer. Then, what if we instead have multiple (say $t$) copies, but x's are freshly random in case (2)? Does it mean that the advantage is at most $t$ times that of the single-copy case? Jul 22, 2023 at 21:51
• @Henry I've added this case, please have a look! Jul 24, 2023 at 7:41