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

Question

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?

Answer 1

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.