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 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
Eigen-decompositions; the two eigenbases need not coincide.
Expand in the eigenbasis of . The matrix is doubly stochastic.
Concavity of (Jensen), since each row of sums to 1.
The columns of also sum to 1, so is a probability vector, and the classical Gibbs inequality applies. Tracing the equality conditions shows iff .
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 is small, then can be approximately recovered from alone by a channel acting on .
The Holevo bound, proved
Alice draws with probability and sends . Bob measures a POVM and obtains with . Encode the whole situation in one classical-quantum state.
is a classical register holding Alice's choice.
is block diagonal, so . The Holevo information is the quantum mutual information of the cq state.
Bob's measurement is a channel with a classical output.
Applied to the cq state it yields the classical joint distribution ; applied to the product of marginals it yields the product of marginals.
Monotonicity of relative entropy.
Alice sends or with equal probability. What is the Holevo information , in bits? (Hint: the states commute, so is also the accessible information.)
Show the answer
0.31 bits
The average state is , with . Subtract : . Measuring gives a "Z-channel" with , the same value, as the equality condition promises.
Accessible information
The accessible information 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 of them ( for real ensembles).
| Ensemble (equiprobable) | Holevo | Accessible |
|---|---|---|
| 1 | 1 (commuting: measure ) | |
| (overlap ) | ||
| Two pure states with overlap | , Helstrom basis (Levitin) | |
| Trine (three states apart) | 1 | , three-outcome POVM |
Two facts close the gap and open new ones. First, on many copies, is achievable: with collective measurements across uses, Bob can decode at any rate below (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 random bits either directly or after Hadamards on every qubit, choosing which by one secret bit. Bob's accessible information is only , yet learning that one bit raises it to : one bit of communication unlocks 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 , so 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 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 bits.
Random access codes and the frontier
Holevo forbids storing bits in fewer than qubits if Bob must recover all of them. What if he needs only one bit of his choice? An quantum random access code (QRAC) encodes into qubits so that every can be decoded with probability at least . A code exists: map to the Bloch vector and measure for or for , succeeding with probability (Ambainis, Nayak, Ta-Shma & Vazirani).
Chain rule for mutual information, with uniform on and the -qubit code state.
The bits are independent, so ; then monotonicity (adding a system cannot decrease mutual information), which is strong subadditivity.
is the output of Bob's decoder for bit : data processing, then Fano's inequality, for .
Combine, and bound the mutual information of a cq state by the entropy of its quantum part. For the code: , consistent. As the bound becomes trivial, but no constant allows .
You want to encode bits so that any one of them can be read with probability at least . By Nayak's bound, at least how many qubits do you need?
Show the answer
531 qubits
, so . Quantum random access codes save something, but only a constant factor: compare 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
- with equality iff (Klein), and never increases under channels (Lindblad–Uhlmann), equivalent to strong subadditivity.
- Holevo: of the cq state, and data processing gives , with equality iff the states commute.
- Accessible information can be strictly below (trine: vs ), but is achievable asymptotically with collective measurements. Locking shows accessible information is a poor security measure.
- Nayak's bound 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.
When is the quantum relative entropy equal to zero?
- Whenever and commute
- Exactly when
- Whenever and have the same eigenvalues
- When their supports are orthogonal
Show the answer
B. Exactly when
Klein's inequality gives with equality iff . That makes a (non-symmetric) measure of distinguishability.
In the modern proof of the Holevo bound, which property does the essential work?
- Concavity of the von Neumann entropy
- The Schmidt decomposition of
- Unitary invariance of the entropy
- 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 , apply the measurement channel to both arguments, and the relative entropy can only drop, to .
For which equiprobable ensemble does the best single-copy measurement attain the Holevo information exactly?
- The trine
Show the answer
A.
and commute, so measuring in their common eigenbasis gives bits. The other ensembles contain non-commuting states, and for them .
The random access code stores 2 bits in one qubit. Why does this not contradict the Holevo bound?
- It does contradict it; the Holevo bound fails for mixed states
- Because the code uses entanglement
- Each bit is recovered only with probability , so the information actually required is bit, and Bob learns only one bit of his choice
- Because the qubit is measured twice
Show the answer
C. Each bit is recovered only with probability , so the information actually required is bit, and Bob learns only one bit of his choice
Nayak's argument shows the code needs qubits; here . Measuring for disturbs the state, so Bob cannot also learn 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).