Chapter 15

Entropy, accessible information, and the Holevo bound

Alice encodes a message in one qubit and sends it to Bob. A qubit’s state takes continuous parameters to describe, so could it carry many bits? How many can Bob actually recover, and what changes if the two of them shared an entangled pair beforehand?

Before you start: POVMs (Chapter 2); density matrices and their eigenvalues (Chapter 3); Schmidt coefficients (Chapter 7); dense coding (Chapter 9). The last section uses channels (Chapter 13). Logarithms are base two throughout. Notation guide.

Begin with classical uncertainty

In this chapter $X$ and $Y$ denote random variables and $H$ the Shannon entropy, not the Pauli matrices $X,Y$ or the Hadamard gate; $Z$ still denotes the Pauli matrix. For a random variable $X$ with probabilities $p_x$, the Shannon entropy in bits is $H(X)=-\sum_xp_x\log_2p_x$, with $0\log_2 0=0$ by continuity. A certain outcome has entropy zero; a fair binary outcome has entropy one. The binary entropy function is $h_2(p)=-p\log_2p-(1-p)\log_2(1-p)$.

Entropy of a measurement result is not automatically information about a message. Let $X$ be the message and $Y$ the observed outcome. To define their conditional entropy, first fix an observed value $y$ and use the probabilities $p(x|y)=p(x,y)/p(y)$. The remaining uncertainty is $H(X|Y=y)=-\sum_xp(x|y)\log_2p(x|y)$. Average this uncertainty over the observed values to obtain $H(X|Y)=\sum_yp(y)H(X|Y=y)$; outcomes with $p(y)=0$ contribute nothing. Interchanging $X$ and $Y$ defines $H(Y|X)$ in the same way.

Mutual information is the average reduction in uncertainty about the message after seeing the outcome. Start with $H(X)$, subtract what remains, $H(X|Y)$. An equivalent expression subtracts the outcome uncertainty left after the input is specified:

$$I(X:Y)=H(Y)-\sum_xp_xH(Y|X=x)=H(X)-H(X|Y).$$

Consider a fair input bit sent through a device that flips it independently with probability $1/4$. The joint probabilities, arranged with inputs as rows and outputs as columns, are

Both input and output are fair, so $H(X)=H(Y)=1$. After observing $y=0$, Bayes' rule gives $p(x=0|y=0)=(3/8)/(1/2)=3/4$ and $p(x=1|y=0)=1/4$. Observing $y=1$ reverses these probabilities, leaving the same entropy. Therefore

$$\begin{aligned}H(X|Y)&=\tfrac12h_2(1/4)+\tfrac12h_2(1/4)\approx0.811,\\ I(X:Y)&=1-0.811\approx0.189\text{ bits}. \end{aligned}$$

The output is one random bit in every run, yet it removes only about $0.189$ bits of uncertainty on average. If the flip rate becomes $1/2$, every cell of the table is $1/4$: conditioning on either output leaves a fair input and gives zero information. If the flip rate is zero, only the diagonal cells remain and the output determines the input, giving one bit. These limits explain what the subtraction in mutual information measures.

If the conditional distribution of $Y$ is the same for every $x$, then $X$ and $Y$ are independent and the mutual information is zero, even if $Y$ is a perfectly random bit. Communication requires message-dependent statistics.

Compute quantum entropy from eigenvalues

For a density matrix with eigenvalues $\lambda_j$, define

$$S(\rho)=-\operatorname{Tr}(\rho\log_2\rho)=-\sum_j\lambda_j\log_2\lambda_j.$$

A pure state has spectrum $1,0,\ldots$ and entropy zero. The maximally mixed state $I/d$ has entropy $\log_2d$, and no $d$-dimensional state has more: the uniform spectrum maximises the entropy. For a qubit with Bloch-vector length $r$, the eigenvalues are $(1\pm r)/2$, so $S(\rho)=h_2((1+r)/2)$. This depends on the spectrum, not the chosen matrix basis.

In particular $S(|+\rangle\langle+|)=0$, although measuring $Z$ on it produces a fair random bit with Shannon entropy one. The measurement basis creates a distribution that is not the eigenvalue distribution. A pure state is not a promise of deterministic outcomes for every observable.

Entanglement entropy has a restricted domain

For a pure bipartite state with Schmidt coefficients $s_j$, the reduced eigenvalues are $s_j^2$. Its entanglement entropy is $S(\rho_A)=S(\rho_B)=-\sum_js_j^2\log_2s_j^2$. A Bell pair gives one bit of reduced entropy, conventionally one ebit of entanglement; a product gives zero.

This equality is a pure-joint-state statement. The separable mixture $(|00\rangle\langle00|+|11\rangle\langle11|)/2$ also has $S(\rho_A)=S(\rho_B)=1$, yet no entanglement. Reduced entropy alone does not quantify mixed-state entanglement.

Define the communication problem precisely

Every calculation below states three things: what travels from Alice to Bob, what they shared beforehand, and what Bob holds when he decodes. Alice draws $x$ with probability $p_x$, prepares $\rho_x$, and sends the system to Bob. Its average state is $\bar\rho=\sum_xp_x\rho_x$. Bob chooses a positive operator-valued measure (POVM), the general measurement introduced in Chapter 2. Its effects $\{E_y\}$ obey $E_y\ge0$ and $\sum_yE_y=I$, giving $p(y|x)=\operatorname{Tr}(\rho_xE_y)$. These conditional probabilities, together with $p_x$, define a classical joint distribution and hence $I(X:Y)$.

The accessible information is the maximum of that mutual information over Bob's measurements. The Holevo theorem bounds it by

$$I(X:Y)\le\chi,\qquad \chi=S(\bar\rho)-\sum_xp_xS(\rho_x).$$

The theorem is stated here, not proved. Its proof uses quantum entropy inequalities. Since $S(\rho_x)\ge0$ and $S(\bar\rho)\le\log_2d$, an ensemble received on a $d$-dimensional system has $\chi\le\log_2d$. This statement applies to the whole system available for decoding, with any message-correlated side information accounted for.

Two ensembles with the same average and different information

First encode an equally likely bit as $\rho_0=|0\rangle\langle0|$ and $\rho_1=|1\rangle\langle1|$. Their average is $I/2$, with entropy one; each conditional state is pure. Thus $\chi=1$, attained by measuring $Z$.

Now use $\rho_0=\rho_1=I/2$. The average is still $I/2$, but each conditional entropy is one, so $\chi=1-1=0$. For every effect, $p(y|0)=p(y|1)$. The maximally mixed state has one bit of entropy in either example; only the first ensemble carries a bit about the message.

A nonorthogonal encoding

Encode equal-prior bits as $|0\rangle$ and $|+\rangle$. The average and its eigenvalues are

$$\bar\rho=\begin{pmatrix}3/4&1/4\\1/4&1/4\end{pmatrix},\qquad\lambda_\pm=\frac{1\pm1/\sqrt2}{2}.$$

Both signal states are pure, so $\chi=h_2((1+1/\sqrt2)/2)\approx0.601$ bits. This is an upper bound, not a claim that a particular measurement attains it.

For a concrete measurement choose $Z$. Input $0$ gives outcome zero certainly; input $1$ gives zero or one equally. The marginal output has probabilities $3/4,1/4$, so $H(Y)=h_2(1/4)\approx0.811$. Its conditional entropy is $(0+1)/2=0.5$. Therefore $I(X:Y)\approx0.311$ bits, below the bound. An inconclusive outcome in a different measurement must also be included in its joint distribution; a success probability is not interchangeable with mutual information.

Dense coding with all resources included

In Chapter 9's equal-prior dense-coding ensemble, each of the four message-conditioned transmitted-qubit states is $I/2$. On that qubit alone, $\chi=1-1=0$. Bob, however, also possesses the other half of the original Bell pair. After receiving the transmitted half, his four possible joint states are orthogonal pure Bell states. Their average is $I/4$, so

$$\chi_{AB}=S(I/4)-\frac14\sum_{a,b}S(|\beta_{ab}\rangle\langle\beta_{ab}|)=2-0=2.$$

Bob’s Bell measurement acts on two qubits: the one that travelled and his half of the pair shared beforehand. Here it recovers two bits, equal to $\chi$. The accounting is: one qubit travels, one entangled pair (an ebit) was shared before the message was chosen, and Bob measures two qubits. The one-qubit dimension bound cannot be applied to a decoder holding a two-qubit message-dependent state.

Noise and information are not the same as mixedness

A channel can lower entropy: full amplitude damping sends $I/2$ to the pure ground state. It can nevertheless destroy message information. If it maps both $|0\rangle$ and $|1\rangle$ to $|0\rangle$, their output ensemble has $\chi=0$, although its average is now pure.

The relevant monotonicity theorem is that applying the same channel to every signal state cannot increase the Holevo quantity. This is a data-processing statement about the ensemble, not a claim that every individual state's entropy grows. Entropy, entanglement, and accessible classical information answer different questions; their assumptions determine which calculation is appropriate.

Where this leaves us

One transmitted qubit, with nothing shared beforehand, gives Bob at most one bit, however many continuous parameters Alice used to prepare it: the Holevo quantity of a qubit ensemble is at most $\log_22=1$. That bound, $\chi$, is a ceiling on what any measurement recovers; a particular measurement can recover less, as the $Z$ measurement does for $|0\rangle$ or $|+\rangle$, $0.311$ bits against $0.601$. Nonorthogonal encodings stay below one bit, and a message-independent state gives nothing, even though its entropy is maximal. With one entangled pair shared beforehand, the same single transmitted qubit carries two bits: one qubit travels, but Bob measures two, the transmitted qubit together with his half of the pair.

That answer is typical of what the book has found quantum information allows. It does not allow copying an unknown state, sending a message faster than a classical signal, or packing more than one bit into a qubit alone. It does allow correlations that no local classical model reproduces; moving an unknown state with two classical bits and a shared pair; answering some questions with fewer queries than any exact classical method, and finding periods through Fourier sampling, when the problem has the right structure and the oracle or arithmetic can be built; and protecting amplitudes against errors without reading them. Each of those came with its conditions, and the conditions are part of the result.

Problems

1. Send equally likely $|0\rangle$ and $|1\rangle$ through a bit-flip channel with flip probability $p$. Compute $\chi$ and the information obtained by measuring $Z$.

Worked answer

The channel takes input zero to $\rho'_0=(1-p)|0\rangle\langle0|+p|1\rangle\langle1|$ and input one to $\rho'_1=p|0\rangle\langle0|+(1-p)|1\rangle\langle1|$. Both have eigenvalues $p,1-p$, while their equal average is $I/2$.

$$\chi=S(I/2)-\tfrac12S(\rho'_0)-\tfrac12S(\rho'_1)=1-h_2(p).$$

Measuring $Z$ gives a fair output bit: $H(Y)=1$. With either input fixed, the output probabilities are $p,1-p$, so $H(Y|X)=\frac12h_2(p)+\frac12h_2(p)=h_2(p)$. Hence $I(X:Y)=1-h_2(p)$, attaining the bound. At $p=1/2$ it vanishes; at $p=1$ the output identifies the input after a known inversion.

2. Mix $|+\rangle$ and $|-\rangle$ with probabilities $3/4$ and $1/4$. Find $\chi$ and a measurement attaining it.

Worked answer

The two conditional states are pure and orthogonal, with zero entropy. Their average is $\bar\rho=\frac34|+\rangle\langle+|+\frac14|-\rangle\langle-|$, already diagonal in the $X$ eigenbasis. Therefore

$$\chi=S(\bar\rho)=-\tfrac34\log_2(3/4)-\tfrac14\log_2(1/4)\approx0.811.$$

Measuring $X$ identifies $+$ or $-$ without error, so the conditional input entropy $H(\text{message}|\text{outcome})$ is zero. Mutual information then equals the input entropy, $h_2(1/4)\approx0.811$ bits. The value is below one because the source selects its messages with unequal probabilities, not because decoding loses any of them.

References and further reading

Nielsen & Chuang, §11.1–11.3 (classical and quantum entropy), §11.4 (strong subadditivity), and §12.1 (accessible information and the Holevo bound). Proofs of the entropy and data-processing theorems are outside this chapter.