Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Von Neumann Entropy & the Holevo Bound

Why n qubits carry at most n classical bits.

A qubit state is described by two real parameters, so it seems to hold unlimited information. Holevo's theorem says you can never get more than one bit out. The proof is a two-line consequence of a single deep fact, that relative entropy cannot increase under quantum channels, and the same fact bounds random access codes, governs what measurements can extract, and underlies every converse in quantum Shannon theory.

What you’ll learn

  • Define quantum relative entropy, prove Klein's inequality, and state its monotonicity under channels and the equivalence with strong subadditivity.
  • Prove the Holevo bound I(X:Y)≤χI(X{:}Y)\le\chi from data processing, and state when it is tight.
  • Compute the Holevo information and accessible information of standard ensembles, and explain why they can differ.
  • Prove Nayak's bound on quantum random access codes from the Holevo bound and Fano's inequality.

Relative entropy and its monotonicity

DerivationKlein's inequality: D(ρ‖σ) ≥ 0
  1. ρ=∑ipi∣i⟩ ⁣⟨i∣,σ=∑jqj∣j⟩ ⁣⟨j∣\rho=\sum_ip_i\dyad{i},\qquad \sigma=\sum_jq_j\dyad{j}

    Eigen-decompositions; the two eigenbases need not coincide.

  2. D(ρ∥σ)=∑ipilog⁡pi−∑ipi∑jPijlog⁡qj,Pij=∣⟨i∣j⟩∣2D(\rho\Vert\sigma)=\sum_ip_i\log p_i-\sum_ip_i\sum_jP_{ij}\log q_j,\qquad P_{ij}=\abs{\braket{i|j}}^2

    Expand ⟨i∣log⁡σ∣i⟩\bra i\log\sigma\ket i in the eigenbasis of σ\sigma. The matrix PP is doubly stochastic.

  3. ∑jPijlog⁡qj ≤ log⁡ri,ri:=∑jPijqj\sum_jP_{ij}\log q_j\ \le\ \log r_i,\qquad r_i:=\sum_jP_{ij}q_j

    Concavity of log⁡\log (Jensen), since each row of PP sums to 1.

  4. D(ρ∥σ) ≥ ∑ipilog⁡piri=D(p∥r) ≥ 0D(\rho\Vert\sigma)\ \ge\ \sum_ip_i\log\frac{p_i}{r_i}=D(p\Vert r)\ \ge\ 0

    The columns of PP also sum to 1, so rr is a probability vector, and the classical Gibbs inequality applies. Tracing the equality conditions shows D(ρ∥σ)=0D(\rho\Vert\sigma)=0 iff ρ=σ\rho=\sigma. ■\blacksquare

Everything that follows is a consequence of this one inequality. Its proof is genuinely hard: Lieb's concavity theorem (1973) is the classical route, and modern proofs use operator convexity or interpolation. Fawzi & Renner (2015) strengthened it to a robust form: if I(A:C∣B)I(A{:}C|B) is small, then CC can be approximately recovered from BB alone by a channel acting on BB.

The Holevo bound, proved

Alice draws xx with probability pxp_x and sends ρx\rho_x. Bob measures a POVM {Ey}\{E_y\} and obtains YY with p(y∣x)=Tr⁡(Eyρx)p(y|x)=\Tr(E_y\rho_x). Encode the whole situation in one classical-quantum state.

DerivationProof of the Holevo bound
  1. ρXB=∑xpx ∣x⟩ ⁣⟨x∣X⊗ρx\rho_{XB}=\sum_xp_x\,\dyad x_X\otimes\rho_x

    XX is a classical register holding Alice's choice.

  2. I(X:B)ρ=H(p)+S(∑xpxρx)−[H(p)+∑xpxS(ρx)]=χI(X{:}B)_\rho=H(p)+S\Big(\sum_xp_x\rho_x\Big)-\Big[H(p)+\sum_xp_xS(\rho_x)\Big]=\chi

    ρXB\rho_{XB} is block diagonal, so S(XB)=H(p)+∑xpxS(ρx)S(XB)=H(p)+\sum_xp_xS(\rho_x). The Holevo information is the quantum mutual information of the cq state.

  3. M(σ)=∑yTr⁡(Eyσ) ∣y⟩ ⁣⟨y∣Y\mathcal M(\sigma)=\sum_y\Tr(E_y\sigma)\,\dyad y_Y

    Bob's measurement is a channel B→YB\to Y with a classical output.

  4. (id⊗M)(ρXB)=ρXY,(id⊗M)(ρX⊗ρB)=ρX⊗ρY(\mathrm{id}\otimes\mathcal M)(\rho_{XB})=\rho_{XY},\qquad (\mathrm{id}\otimes\mathcal M)(\rho_X\otimes\rho_B)=\rho_X\otimes\rho_Y

    Applied to the cq state it yields the classical joint distribution pxp(y∣x)p_xp(y|x); applied to the product of marginals it yields the product of marginals.

  5. I(X:Y)=D(ρXY∥ρX⊗ρY) ≤ D(ρXB∥ρX⊗ρB)=I(X:B)=χI(X{:}Y)=D\big(\rho_{XY}\Vert\rho_X\otimes\rho_Y\big)\ \le\ D\big(\rho_{XB}\Vert\rho_X\otimes\rho_B\big)=I(X{:}B)=\chi

    Monotonicity of relative entropy. ■\blacksquare

Predict before you look

Alice sends ρ0=∣0⟩ ⁣⟨0∣\rho_0=\dyad0 or ρ1=I/2\rho_1=\id/2 with equal probability. What is the Holevo information χ\chi, in bits? (Hint: the states commute, so χ\chi is also the accessible information.)

Show the answer

0.31 bits

The average state is diag⁡(34,14)\diag(\tfrac34,\tfrac14), with S=h(14)≈0.811S=h(\tfrac14)\approx0.811. Subtract 12S(ρ0)+12S(ρ1)=12\tfrac12S(\rho_0)+\tfrac12S(\rho_1)=\tfrac12: χ≈0.311\chi\approx0.311. Measuring ZZ gives a "Z-channel" with I=h(14)−12I=h(\tfrac14)-\tfrac12, the same value, as the equality condition promises.

Accessible information

The accessible information Iacc=max⁡{Ey}I(X:Y)I_{\rm acc}=\max_{\{E_y\}}I(X{:}Y) is what one copy of the ensemble actually yields. It is a non-convex optimization with no closed form in general, but its structure is known: by Davies' theorem (1978) the optimum is attained by a POVM with rank-one elements, at most d2d^2 of them (d(d+1)/2d(d+1)/2 for real ensembles).

Ensemble (equiprobable)Holevo χ\chiAccessible IaccI_{\rm acc}
∣0⟩,∣1⟩\ket0,\ket111 (commuting: measure ZZ)
∣0⟩,∣+⟩\ket0,\ket+ (overlap c=1/2c=1/\sqrt2)h(cos⁡2π8)≈0.60h(\cos^2\tfrac\pi8)\approx0.601−h(sin⁡2π8)≈0.401-h(\sin^2\tfrac\pi8)\approx0.40
Two pure states with overlap cch(1+c2)h\big(\tfrac{1+c}{2}\big)1−h(1−1−c22)1-h\big(\tfrac{1-\sqrt{1-c^2}}{2}\big), Helstrom basis (Levitin)
Trine (three states 120°120° apart)1log⁡232≈0.585\log_2\tfrac32\approx0.585, three-outcome POVM
For pure states χ=S(ρ)\chi=S(\rho). The gap between χ\chi and IaccI_{\rm acc} is real: Holevo is an upper bound for one copy, not a formula.

Two facts close the gap and open new ones. First, on many copies, χ\chi is achievable: with collective measurements across nn uses, Bob can decode at any rate below χ\chi (Holevo–Schumacher–Westmoreland, see the capacities lesson). Peres & Wootters (1991) already observed that joint measurements on product states can beat any sequence of separate measurements.

Second, accessible information behaves badly as a security measure. In the locking example of DiVincenzo, Horodecki, Leung, Smolin & Terhal (2004), Alice encodes nn random bits either directly or after Hadamards on every qubit, choosing which by one secret bit. Bob's accessible information is only n/2n/2, yet learning that one bit raises it to nn: one bit of communication unlocks n/2n/2 bits. Accessible information is not additive in this sense, so it cannot serve as a composable security criterion.

Think first The trine's average state is I/2\id/2, so χ=1\chi=1 bit. Why can't any single-qubit measurement reach it?

Equality in Holevo requires commuting states, and the trine states do not commute. Intuitively, every outcome of a qubit measurement is compatible with at least two of the three states, so some uncertainty about xx always remains. The optimal three-outcome POVM, with elements proportional to projectors onto states orthogonal to each trine state, rules out one message per outcome and leaves the other two equally likely, giving log⁡23−1=log⁡232\log_23-1=\log_2\tfrac32 bits.

Random access codes and the frontier

Holevo forbids storing nn bits in fewer than nn qubits if Bob must recover all of them. What if he needs only one bit of his choice? An (n,m,p)(n,m,p) quantum random access code (QRAC) encodes x∈{0,1}nx\in\{0,1\}^n into mm qubits so that every xix_i can be decoded with probability at least pp. A (2,1,cos⁡2π8)(2,1,\cos^2\frac\pi8) code exists: map x1x2x_1x_2 to the Bloch vector 12((−1)x2x^+(−1)x1z^)\tfrac{1}{\sqrt2}\big((-1)^{x_2}\hat x+(-1)^{x_1}\hat z\big) and measure ZZ for x1x_1 or XX for x2x_2, succeeding with probability 1+1/22≈0.854\tfrac{1+1/\sqrt2}{2}\approx0.854 (Ambainis, Nayak, Ta-Shma & Vazirani).

DerivationNayak's bound: m ≥ (1 − h(p)) n
  1. I(X:B)=∑i=1nI(Xi:B ∣ X1⋯Xi−1)I(X{:}B)=\sum_{i=1}^nI\big(X_i{:}B\,\big|\,X_1\cdots X_{i-1}\big)

    Chain rule for mutual information, with XX uniform on {0,1}n\{0,1\}^n and BB the mm-qubit code state.

  2. I(Xi:B ∣ X<i)=I(Xi:BX<i) ≥ I(Xi:B)I\big(X_i{:}B\,\big|\,X_{<i}\big)=I\big(X_i{:}BX_{<i}\big)\ \ge\ I(X_i{:}B)

    The bits are independent, so I(Xi:X<i)=0I(X_i{:}X_{<i})=0; then monotonicity (adding a system cannot decrease mutual information), which is strong subadditivity.

  3. I(Xi:B) ≥ I(Xi:Yi) ≥ 1−h(p)I(X_i{:}B)\ \ge\ I(X_i{:}Y_i)\ \ge\ 1-h(p)

    YiY_i is the output of Bob's decoder for bit ii: data processing, then Fano's inequality, H(Xi∣Yi)≤h(p)H(X_i|Y_i)\le h(p) for p≥12p\ge\tfrac12.

  4. n(1−h(p)) ≤ I(X:B) ≤ S(B) ≤ mn\big(1-h(p)\big)\ \le\ I(X{:}B)\ \le\ S(B)\ \le\ m

    Combine, and bound the mutual information of a cq state by the entropy of its quantum part. ■\blacksquare For the (2,1)(2,1) code: 2(1−h(0.854))≈0.80≤12(1-h(0.854))\approx0.80\le1, consistent. As p→12p\to\tfrac12 the bound becomes trivial, but no constant p>12p>\tfrac12 allows m=o(n)m=o(n).

Predict before you look

You want to encode n=1000n=1000 bits so that any one of them can be read with probability at least 0.90.9. By Nayak's bound, at least how many qubits do you need?

Show the answer

531 qubits

h(0.9)≈0.469h(0.9)\approx0.469, so m≥1000×(1−0.469)≈531m\ge1000\times(1-0.469)\approx531. Quantum random access codes save something, but only a constant factor: compare m=1000m=1000 for perfect recall. Nayak's bound was first used for lower bounds on quantum finite automata, and it remains a standard tool in quantum communication complexity.

Key takeaways

  • D(ρ∥σ)≥0D(\rho\Vert\sigma)\ge0 with equality iff ρ=σ\rho=\sigma (Klein), and DD never increases under channels (Lindblad–Uhlmann), equivalent to strong subadditivity.
  • Holevo: χ=I(X:B)\chi=I(X{:}B) of the cq state, and data processing gives I(X:Y)≤χ≤log⁡2dI(X{:}Y)\le\chi\le\log_2d, with equality iff the states commute.
  • Accessible information can be strictly below χ\chi (trine: 0.5850.585 vs 11), but χ\chi is achievable asymptotically with collective measurements. Locking shows accessible information is a poor security measure.
  • Nayak's bound m≥(1−h(p)) nm\ge(1-h(p))\,n for random access codes follows from Holevo, the chain rule and Fano.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

When is the quantum relative entropy D(ρ∥σ)D(\rho\Vert\sigma) equal to zero?

  1. Whenever ρ\rho and σ\sigma commute
  2. Exactly when ρ=σ\rho=\sigma
  3. Whenever ρ\rho and σ\sigma have the same eigenvalues
  4. When their supports are orthogonal
Show the answer

B. Exactly when ρ=σ\rho=\sigma

Klein's inequality gives D≥0D\ge0 with equality iff ρ=σ\rho=\sigma. That makes DD a (non-symmetric) measure of distinguishability.

Question 2

In the modern proof of the Holevo bound, which property does the essential work?

  1. Concavity of the von Neumann entropy
  2. The Schmidt decomposition of ρXB\rho_{XB}
  3. Unitary invariance of the entropy
  4. Monotonicity of relative entropy (data processing) under Bob's measurement channel
Show the answer

D. Monotonicity of relative entropy (data processing) under Bob's measurement channel

Write χ=I(X:B)=D(ρXB∥ρX⊗ρB)\chi=I(X{:}B)=D(\rho_{XB}\Vert\rho_X\otimes\rho_B), apply the measurement channel to both arguments, and the relative entropy can only drop, to I(X:Y)I(X{:}Y).

Question 3

For which equiprobable ensemble does the best single-copy measurement attain the Holevo information exactly?

  1. {∣0⟩ ⁣⟨0∣, I/2}\{\dyad0,\ \id/2\}
  2. {∣0⟩, ∣+⟩}\{\ket0,\ \ket+\}
  3. The trine
  4. {∣0⟩,∣1⟩,∣+⟩,∣−⟩}\{\ket0,\ket1,\ket+,\ket-\}
Show the answer

A. {∣0⟩ ⁣⟨0∣, I/2}\{\dyad0,\ \id/2\}

∣0⟩ ⁣⟨0∣\dyad0 and I/2\id/2 commute, so measuring in their common eigenbasis gives I(X:Y)=χ≈0.31I(X{:}Y)=\chi\approx0.31 bits. The other ensembles contain non-commuting states, and for them Iacc<χI_{\rm acc}<\chi.

Question 4

The (2,1,0.854)(2,1,0.854) random access code stores 2 bits in one qubit. Why does this not contradict the Holevo bound?

  1. It does contradict it; the Holevo bound fails for mixed states
  2. Because the code uses entanglement
  3. Each bit is recovered only with probability 0.8540.854, so the information actually required is 2 (1−h(0.854))≈0.80≤12\,(1-h(0.854))\approx0.80\le1 bit, and Bob learns only one bit of his choice
  4. Because the qubit is measured twice
Show the answer

C. Each bit is recovered only with probability 0.8540.854, so the information actually required is 2 (1−h(0.854))≈0.80≤12\,(1-h(0.854))\approx0.80\le1 bit, and Bob learns only one bit of his choice

Nayak's argument shows the code needs m≥n(1−h(p))m\ge n(1-h(p)) qubits; here 0.80≤10.80\le1. Measuring for x1x_1 disturbs the state, so Bob cannot also learn x2x_2 reliably: the total information he can extract stays below one bit.

Further reading

  • A. S. Holevo, "Bounds for the quantity of information transmitted by a quantum communication channel", Problems of Information Transmission 9, 177 (1973).
  • E. H. Lieb & M. B. Ruskai, "Proof of the strong subadditivity of quantum-mechanical entropy", Journal of Mathematical Physics 14, 1938 (1973).
  • G. Lindblad, "Completely positive maps and entropy inequalities", Communications in Mathematical Physics 40, 147 (1975).
  • A. Nayak, "Optimal lower bounds for quantum automata and random access codes", Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999).
  • M. M. Wilde, Quantum Information Theory, 2nd ed., Chapters 11–12 (Cambridge, 2017).