Holevo's theorem

Proof

Consider the composite system that describes the entire communication process, which involves Alice's classical input ${\displaystyle X}$, the quantum system ${\displaystyle Q}$, and Bob's classical output ${\displaystyle Y}$. The classical input ${\displaystyle X}$ can be written as a classical register ${\displaystyle {\rho }^X:={\sum }_{x=1}^n{p}_x|x⟩⟨x|}$ with respect to some orthonormal basis ${\displaystyle \{|x⟩{\}}_{x=1}^n}$. By writing ${\displaystyle X}$ in this manner, the von Neumann entropy ${\displaystyle S(X)}$ of the state ${\displaystyle {\rho }^X}$ corresponds to the Shannon entropy ${\displaystyle H(X)}$ of the probability distribution ${\displaystyle \{p_x{\}}_{x=1}^n}$:

${\displaystyle S(X)=-\mathrm{tr}\left({\rho }^X\log {\rho }^X\right)=-\mathrm{tr}\left(\sum _{x=1}^n{p}_x\log p_x|x⟩⟨x|\right)=-\sum _{x=1}^n{p}_x\log p_x=H(X).}$

The initial state of the system, where Alice prepares the state ${\displaystyle {\rho }_x}$ with probability ${\displaystyle p_x}$, is described by

${\displaystyle {\rho }^{XQ}:=\sum _{x=1}^n{p}_x|x⟩⟨x|\otimes {\rho }_x.}$

Afterwards, Alice sends the quantum state to Bob. As Bob only has access to the quantum system ${\displaystyle Q}$ but not the input ${\displaystyle X}$, he receives a mixed state of the form ${\displaystyle \rho :={\mathrm{tr}}_X\left({\rho }^{XQ}\right)={\sum }_{x=1}^n{p}_x{\rho }_x}$. Bob measures this state with respect to the POVM elements ${\displaystyle \{E_y{\}}_{y=1}^m}$, and the probabilities ${\displaystyle \{q_y{\}}_{y=1}^m}$ of measuring the outcomes ${\displaystyle y=1,2,\dots ,m}$ form the classical output ${\displaystyle Y}$. This measurement process can be described as a quantum instrument

${\displaystyle {\mathcal{E}}^Q({\rho }_x)=\sum _{y=1}^m{q}_{y|x}{\rho }_{y|x}\otimes |y⟩⟨y|,}$

where ${\displaystyle q_{y|x}=\mathrm{tr}\left(E_y{\rho }_x\right)}$ is the probability of outcome ${\displaystyle y}$ given the state ${\displaystyle {\rho }_x}$, while ${\displaystyle {\rho }_{y|x}=W\sqrt{E_y}{\rho }_x\sqrt{E_y}{W}^{†}/q_{y|x}}$ for some unitary ${\displaystyle W}$ is the normalised post-measurement state. Then, the state of the entire system after the measurement process is

${\displaystyle {\rho }^{X{Q}^{\prime }Y}:=\left[{\mathcal{I}}^X\otimes {\mathcal{E}}^Q\right]\left({\rho }^{XQ}\right)=\sum _{x=1}^n\sum _{y=1}^m{p}_x{q}_{y|x}|x⟩⟨x|\otimes {\rho }_{y|x}\otimes |y⟩⟨y|.}$

Here ${\displaystyle {\mathcal{I}}^X}$ is the identity channel on the system ${\displaystyle X}$. Since ${\displaystyle {\mathcal{E}}^Q}$ is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps, ${\displaystyle S(X:Q^{\prime }Y)\le S(X:Q)}$. Additionally, as the partial trace over ${\displaystyle Q^{\prime }}$ is also completely positive and trace-preserving, ${\displaystyle S(X:Y)\le S(X:Q^{\prime }Y)}$. These two inequalities give

${\displaystyle S(X:Y)\le S(X:Q).}$

On the left-hand side, the quantities of interest depend only on

${\displaystyle {\rho }^{XY}:={\mathrm{tr}}_{Q^{\prime }}\left({\rho }^{X{Q}^{\prime }Y}\right)=\sum _{x=1}^n\sum _{y=1}^m{p}_x{q}_{y|x}|x⟩⟨x|\otimes |y⟩⟨y|=\sum _{x=1}^n\sum _{y=1}^m{p}_{x,y}|x,y⟩⟨x,y|,}$

with joint probabilities ${\displaystyle p_{x,y}=p_x{q}_{y|x}}$. Clearly, ${\displaystyle {\rho }^{XY}}$ and ${\displaystyle {\rho }^Y:={\mathrm{tr}}_X({\rho }^{XY})}$, which are in the same form as ${\displaystyle {\rho }^X}$, describe classical registers. Hence,

${\displaystyle S(X:Y)=S(X)+S(Y)-S(XY)=H(X)+H(Y)-H(XY)=I(X:Y).}$

Meanwhile, ${\displaystyle S(X:Q)}$ depends on the term

${\displaystyle \log {\rho }^{XQ}=\log \left(\sum _{x=1}^n{p}_x|x⟩⟨x|\otimes {\rho }_x\right)=\sum _{x=1}^n|x⟩⟨x|\otimes \log \left(p_x{\rho }_x\right)=\sum _{x=1}^n\log p_x|x⟩⟨x|\otimes I^Q+\sum _{x=1}^n|x⟩⟨x|\otimes \log {\rho }_x,}$

where ${\displaystyle I^Q}$ is the identity operator on the quantum system ${\displaystyle Q}$. Then, the right-hand side is

${\displaystyle \begin{array}{cc}S(X:Q)& =S(X)+S(Q)-S(XQ)\\ & =S(X)+S(\rho )+\mathrm{tr}\left({\rho }^{XQ}\log {\rho }^{XQ}\right)\\ & =S(X)+S(\rho )+\mathrm{tr}\left(\sum _{x=1}^n{p}_x\log p_x|x⟩⟨x|\otimes {\rho }_x\right)+\mathrm{tr}\left(\sum _{x=1}^n{p}_x|x⟩⟨x|\otimes {\rho }_x\log {\rho }_x\right)\\ & =S(X)+S(\rho )+\underset{-S(X)}{\underbrace{\mathrm{tr}\left(\sum _{x=1}^n{p}_x\log p_x|x⟩⟨x|\right)}}+\mathrm{tr}\left(\sum _{x=1}^n{p}_x{\rho }_x\log {\rho }_x\right)\\ & =S(\rho )+\sum _{x=1}^n{p}_x\underset{-S({\rho }_x)}{\underbrace{\mathrm{tr}\left({\rho }_x\log {\rho }_x\right)}}\\ & =S(\rho )-\sum _{x=1}^n{p}_{x}S({\rho }_x),\end{array}}$

which completes the proof.

Comments and remarks

In essence, the Holevo bound proves that given n qubits, although they can "carry" a larger amount of (classical) information (thanks to quantum superposition), the amount of classical information that can be retrieved, i.e. accessed, can be only up to n classical (non-quantum encoded) bits. It was also established, both theoretically and experimentally, that there are computations where quantum bits carry more information through the process of the computation than is possible classically.