4
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Jul 21, 2023 at 8:08
  • 2
    $\begingroup$ Do you have a single copy or multiple copies? $\endgroup$
    – Rammus
    Jul 21, 2023 at 8:08

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$. $\endgroup$ Jul 21, 2023 at 12:36
  • $\begingroup$ @MateusAraújo Oops, you're right! $\endgroup$
    – Tristan Nemoz
    Jul 21, 2023 at 15:02
  • $\begingroup$ 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? $\endgroup$
    – Henry
    Jul 22, 2023 at 21:51
  • $\begingroup$ @Henry I've added this case, please have a look! $\endgroup$
    – Tristan Nemoz
    Jul 24, 2023 at 7:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.