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.


1 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}$.


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} $$


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.

  • 1
    $\begingroup$ Thanks for the detailed answer! I had one followup question. Why is the entropy of the state $\rho$, which is a uniform superposition over $x_0$ and $x_1$ less than n bits? I mean i would have expected that this state has at least n bits of entropy, since on measuring we learn n bits ; but the calculation seems to suggest that there is less than n bits of entropy ; would be very helpful if you could share any intuition. $\endgroup$
    – nishkr
    Aug 5, 2021 at 16:16
  • $\begingroup$ Your intuition applies in the classical setting, i.e. when the pure states $\rho_{x_0,x_1}$ are reliably distinguishable, i.e. orthonormal. Then, by Shannon's noiseless channel coding theorem there are indeed exactly $n$ bits of entropy in $\rho$. However, the pure states $\rho_{x_0,x_1}$ are in fact not orthonormal and therefore Shannon's theorem does not apply. However, its quantum generalization called Schumacher's noiseless channel coding theorem (Th.12.6 on p.544 in N&C, see also discussion on p.54 and box 12.4 on p.547) does apply and states that the entropy is $S(\rho)$ bits. $\endgroup$ Aug 5, 2021 at 17:19
  • 1
    $\begingroup$ IOW, the TL;DR is: the entropy is $<n$ because the pure states $\rho_{x_0,x_1}$ are not orthonormal. (Great questions BTW.) $\endgroup$ Aug 5, 2021 at 18:06
  • $\begingroup$ Hi, I was trying to write this down formally, but I am getting stuck. How do I argue the last part (the conclusion part above) - i.e. $H_{min}(X |$ residual quantum state of adv $) \approx n$? The problem I am facing is this latter thing looks like quantum conditional min entropy, while Holevo's bound only says about $H_{min}(X | Y)$ - where Y is the measurement outcome of the other party. The difference is the latter is classical conditional min entropy, while we want quantum conditional min entropy - and it is perhaps more than just this - for eg, how do we know the adv did indeed measure? $\endgroup$
    – nishkr
    Sep 23, 2021 at 20:55
  • $\begingroup$ ^To elaborate more on this, maybe Bob did not measure the state, but only guessed everything - that would mean he still has the state and $H_{min}(X | \text{residual state of Bob}) $ is very less. But this probably doesn't happen since if $x_0,x_1$ are long, Bob can only guess with low probability. I am probably just missing some simple entropy argument and would really appreciate if you can clear this up. $\endgroup$
    – nishkr
    Sep 23, 2021 at 21:02

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.