How to prove that $\frac{| x_0 \rangle + | x_1 \rangle}{\sqrt{2}}$ hides one of $x_0$ or $x_1$?

Question

I create a quantum state $| \psi \rangle = \frac{| x_0 \rangle + | x_1 \rangle}{\sqrt{2}}$ for a randomly chosen $x_0,x_1$ of 50 bits. I give this quantum state $|\psi \rangle$ to you and you return me back $x_0$. How do I prove that conditioned on you returning me the correct $x_0$, the string $x_1$ is totally hidden from you? i.e. if I now give you either $x_1$ or a uniformly random string of same number of bits, you can't distinguish between them with probability better than $0.5$. This certainly seems true, because if you can return me back the correct/same $x_0$, it must be the case that the system collapsed to $|x_0 \rangle$ and hence $x_1$ is hidden from your point of view. But how would I go about proving this using information theoretic tools? Perhaps we can somehow show that there is entropy in $x_1$ from the receiver's point of view. But I am not sure on how to do this.

Answer 1

We can bound the amount of information that can be retrieved from $|\psi\rangle$ using Holevo's bound.

Alice and Bob

Let us first reformulate the situation in the terms usually employed in the context of Holevo's bound. Suppose Alice chooses two $n$-bit strings $x_0$ and $x_1$ independently and uniformly at random. Let $X$ represent the random variable associated with Alice's choice. Thus, for any $n$-bit strings $x_0$ and $x_1$ we have $P(X=x_0x_1)=p_{x_0,x_1}=2^{-2n}$. Having chosen $x_0$ and $x_1$, Alice prepares the state

$$ \rho_{x_0,x_1} = \left(\frac{|x_0\rangle+|x_1\rangle}{\sqrt{2}}\right)\left(\frac{\langle x_0|+\langle x_1|}{\sqrt{2}}\right) $$

if $x_0\ne x_1$ and $\rho_{x_0,x_0} = |x_0\rangle\langle x_0|$ otherwise. She then sends the state to Bob who performs some measurement on $\rho_{x_0,x_1}$ obtaining a classical outcome represented by the random variable $Y$.

Holevo's theorem

Holevo's theorem says that the mutual information $I(X : Y)$ between $X$ and $Y$ is bounded by

$$ I(X:Y) \le S(\rho) - \sum_{x_0,x_1} p_{x_0,x_1}S(\rho_{x_0,x_1})\tag1 $$

where $\rho = \sum_{x_0,x_1} p_{x_0,x_1}\rho_{x_0,x_1}$.

Entropy

Now, all the states $\rho_{x_0,x_1}$ are pure, so the second term on the right hand side of $(1)$ is zero. In order to evaluate the the first term, let us first compute

$$ \begin{align} \rho &= \sum_{x_0,x_1} p_{x_0,x_1}\rho_{x_0,x_1} \\ &= \sum_{x_0} \frac{1}{2^{2n}}|x_0\rangle\langle x_0| + \sum_{x_0\ne x_1} \frac{1}{2^{2n}}\left(\frac{|x_0\rangle+|x_1\rangle}{\sqrt{2}}\right)\left(\frac{\langle x_0|+\langle x_1|}{\sqrt{2}}\right)\\ &= \frac{I}{2^{2n}} + \frac{1}{2^{2n+1}} \sum_{x_0\ne x_1} |x_0\rangle\langle x_0| + |x_0\rangle\langle x_1| + |x_1\rangle\langle x_0| + |x_1\rangle\langle x_1| \\ &= \frac{I}{2^{2n}} + \frac{2}{2^{2n+1}} \sum_{x_0\ne x_1} |x_0\rangle\langle x_0| + |x_0\rangle\langle x_1|\\ &= \frac{I}{2^{2n}} + \frac{1}{2^{2n}} \left((2^n-2) I + 2^n|\phi\rangle\langle\phi|\right) \\ &= \frac{(2^n - 1)I}{2^{2n}} + \frac{|\phi\rangle\langle\phi|}{2^n} \end{align} $$

where $|\phi\rangle=\frac{1}{\sqrt{2^n}}\sum_i|i\rangle$ is the uniform superposition of all computational basis states of $n$ qubits. Thus, the spectrum of $\rho$ is

$$ \lambda_1 = \frac{2^{n+1}-1}{2^{2n}}, \lambda_2=\dots=\lambda_{2^n}=\frac{2^n-1}{2^{2n}} $$

and its entropy is

$$ \begin{align} S(\rho) &= - \frac{2^{n+1}-1}{2^{2n}}\log\frac{2^{n+1}-1}{2^{2n}} - \frac{(2^n - 1)^2}{2^{2n}}\log\frac{2^n - 1}{2^{2n}} \\ &= 2n - \frac{2^{n+1}-1}{2^{2n}}\log(2^{n+1}-1) - \frac{(2^n - 1)^2}{2^{2n}}\log(2^n - 1). \end{align} $$

For large $n$, the entropy can be approximated as

$$ \begin{align} S(\rho) &\approx 2n - \frac{2^{n+1}-1}{2^{2n}}(n+1) - \frac{(2^n - 1)^2}{2^{2n}}n \\ &= 2n - n - \frac{2^{n+1}-1}{2^{2n}} \\ &\approx n - \frac12. \end{align} $$

Conclusion

Thus, Bob cannot retrieve more than $n$ bits of classical information about $x_0$ and $x_1$ chosen by Alice. In particular, if Bob has already learnt one of the bit strings, e.g. by measuring the state he received in the computational basis, then he already retrieved $n-1$ bits of information ($-1$ corresponds to the fact that Bob doesn't know whether he learnt the first or the second bit string). Thus, by Holevo's bound he cannot learn even one additional bit of information after that.