Holevo Bound

Quantum mechanics lets you prepare a qubit in a superposition of |0\rangle and |1\rangle with any complex amplitudes you like — an uncountably infinite family of states. So in principle, a single qubit "contains" an infinite amount of information: the two real numbers \theta, \phi parameterising the Bloch sphere. Yet when you try to read it out — measure it — you get exactly one classical bit. The infinite-dimensional continuum of amplitudes collapses to a single yes-or-no answer.

The Holevo bound, proved by Alexander Holevo in 1973 and published in his paper on "Bounds for the quantity of information transmitted by a quantum communication channel," is the theorem that makes this observation precise. The classical information you can extract from a quantum system is bounded — and the bound is tight. A d-dimensional quantum system cannot convey more than \log_2 d classical bits, no matter how clever the encoding or the measurement. For a single qubit: one classical bit per transmission, period.

The bound is fundamental. Every quantum-to-classical communication protocol — QKD, quantum fingerprinting, quantum random-access codes, classical capacity of noisy quantum channels — inherits the Holevo bound as its upper ceiling. And yet, as you will see, the bound is violable by entanglement: superdense coding sends 2 classical bits per physical qubit, a fact that initially seems to contradict Holevo but in fact refines it (the pre-shared Bell pair is a separate quantum resource).

This chapter builds the statement, the proof idea, the consequence for n-qubit transmissions, and the reconciliation with superdense coding.

The setup — a classical-quantum channel

Alice wants to send a classical message to Bob using a quantum channel. The setup:

1. Alice's side. Alice has a random classical message X taking values in \{1, 2, \ldots, |\mathcal{X}|\} with probability distribution p(x). Shannon entropy: H(X) = -\sum_x p(x) \log_2 p(x).
2. Encoding. For each possible message value x, Alice prepares a quantum state \rho_x on a d-dimensional Hilbert space \mathcal{H}. These need not be orthogonal; they need not even be pure. The ensemble is \{p(x), \rho_x\}.
3. Transmission. Alice sends the quantum state to Bob over a noiseless channel. If X = x, Bob receives \rho_x.
4. Measurement. Bob performs a measurement described by a POVM \{M_y\}_{y \in \mathcal{Y}} (positive operators summing to identity). The measurement outcome is a classical random variable Y with distribution p(y | x) = \text{tr}(M_y \rho_x) when the input is x.
5. Decoding. Bob uses Y to guess X.

The quantity to maximise is the classical mutual information I(X; Y) between Alice's input and Bob's measurement outcome. The question: how large can I(X; Y) get?

The bound — statement

Reading the statement. The first term S(\rho) is the von Neumann entropy of the average state — the "mixedness" Bob sees if he does not know which x Alice sent. The second term \sum_x p(x) S(\rho_x) is the average entropy of the individual signal states — the mixedness remaining once x is known. The difference is the "reduction in uncertainty due to knowing x" — which is exactly the structural content that a good measurement might extract. Holevo's theorem says: no measurement can extract more classical information than this difference.

For a pure-state ensemble (each \rho_x = |\psi_x\rangle\langle\psi_x|), S(\rho_x) = 0 for all x, so

This special case is often the one you meet first.

Why the bound uses S(\rho_x) for each x and not just S(\rho): if Alice's signal states \rho_x are themselves already mixed (not pure), part of the "uncertainty in \rho" comes from the internal noise of each \rho_x, which Bob cannot hope to resolve. The Holevo quantity subtracts that intrinsic noise, leaving only the distinguishable classical-ensemble component as an upper bound on extractable information.

Proof idea — strong subadditivity in one line

The modern proof of the Holevo bound is a direct application of strong subadditivity (Lieb-Ruskai 1973) of von Neumann entropy. You will not need the whole proof for this chapter, but the three-line idea is worth seeing.

Consider a tripartite system X M Q:

• X is a classical register holding Alice's message (a diagonal density matrix \rho_X = \sum_x p(x) |x\rangle\langle x|).
• Q is the quantum channel, in state \rho_x conditional on X = x.
• M is Bob's measurement ancilla that, after a unitary interaction with Q, holds the outcome Y.

The joint state before measurement is \rho_{XQ} = \sum_x p(x) |x\rangle\langle x|_X \otimes \rho_{x,Q}. Compute its Holevo quantity: by direct calculation, I(X; Q) = \chi in the quantum mutual information sense. Now perform Bob's measurement, coupling Q to M and then tracing out Q. By the data-processing inequality (a consequence of strong subadditivity),

Why this is a one-line proof: the whole Holevo bound reduces to "measurement cannot increase classical mutual information with a reference register," which is what the quantum data-processing inequality says. Strong subadditivity is the deeper theorem underneath, and Lieb-Ruskai's 1973 proof of it unlocks Holevo's 1973 bound as an immediate corollary — the two theorems appeared in the same year for a reason.

Holevo's original 1973 proof used a different route — direct manipulation of entropies and Klein's inequality — but the strong-subadditivity proof has become standard. Nielsen-Chuang §12.1 [3] spells out both arguments.

Consequences

n qubits \leq n classical bits

Take an n-qubit system (d = 2^n). Any ensemble of states on this system has average \rho with S(\rho) \leq \log_2 2^n = n. So by the Holevo bound,

You cannot extract more than n classical bits from n transmitted qubits. The Bloch sphere's continuum of amplitudes is inaccessible in any single-shot measurement. What looked like infinite information content in the quantum state turns out to be, from a classical-extraction perspective, bounded by the number of qubits.

This is a statement with physical bite. It says that a quantum computer with n qubits, no matter how cleverly programmed, cannot output more than n classical bits per "run" — because the output is a quantum measurement, and every measurement on an n-qubit register produces at most n classical bits. Quantum speedup, where it exists, is not about transmitting more information; it is about computing answers whose classical transmission is bounded by the same n-bit ceiling.

Non-orthogonal states lose information

Suppose Alice encodes two equally likely messages into two non-orthogonal pure states: |\psi_0\rangle and |\psi_1\rangle with |\langle\psi_0|\psi_1\rangle| = c \in (0, 1). The average state is \rho = \tfrac{1}{2}|\psi_0\rangle\langle\psi_0| + \tfrac{1}{2}|\psi_1\rangle\langle\psi_1|. Its eigenvalues are \lambda_\pm = (1 \pm c)/2, and

At c = 0 (orthogonal states): \chi = H(1/2) = 1 bit — perfect distinguishability, full bit extracted. At c = 1 (identical states): \chi = H(1) = 0 — no information, the states are the same.

Intermediate c: for c = 1/\sqrt 2 (the angle between |0\rangle and |+\rangle), \chi = H((1 + 1/\sqrt 2)/2) \approx H(0.854) \approx 0.601 bits. Alice's message is worth 1 classical bit (uniformly random between two outcomes), but Bob can recover at most 0.601 bits because the states are not orthogonal. The remaining 0.399 bits are irrecoverably mixed into quantum noise — Holevo is telling you that non-orthogonality costs information, quantitatively.

This is why QKD protocols like BB84 are secure: Eve, limited by Holevo, cannot fully read the quantum signals that Alice and Bob exchange, and her ignorance can be converted to cryptographic security.

Superdense coding — the apparent violation

Superdense coding is a protocol in which Alice sends 2 classical bits to Bob by transmitting a single qubit. On the face of it, this violates the Holevo bound: one qubit, two bits extracted. How?

The answer is that superdense coding consumes a pre-shared entangled Bell pair (one ebit) as a resource. The combined resource budget is 1 qubit transmitted plus 1 ebit consumed, for a total of 2 qubits of quantum resource. The 2 classical bits extracted honour a generalised Holevo-style accounting: 2 classical bits in, 2 quantum resources out. The Holevo bound on the transmitted qubit alone, taken in isolation, is still 1 bit — Alice's single qubit, untouched by the pre-shared entanglement, is in the maximally mixed state \rho = I/2, which has exactly \chi = S(I/2) = 1 bit of Holevo quantity.

The resolution is that the pre-shared Bell pair is itself a quantum resource carrying one ebit of entanglement, and consuming it counts toward Alice's "quantum budget." Superdense coding is a proof of the entanglement-assisted classical capacity theorem: with free pre-shared entanglement, the classical capacity per qubit is 2 \log_2 d, exactly twice the Holevo limit. Without pre-shared entanglement, it is \log_2 d.

This is the cleanest example of "quantum resources are a zoo, not a single quantity." Qubits, ebits, classical bits, and cbits are distinct resources with distinct exchange rates. The Holevo bound fixes the exchange rate between qubits and classical bits; entanglement-assisted protocols consume a second resource (ebits) to beat that rate in a limited sense.

The HSW theorem — tightness at capacity

The Holevo bound is an upper bound. Is it tight? The answer is yes, asymptotically. The Holevo-Schumacher-Westmoreland (HSW) theorem (1996-97) [hsw-theorem] says:

For any classical-quantum channel x \mapsto \rho_x, the classical capacity is

C \;=\; \max_{\{p(x), \rho_x\}} \chi(\{p(x), \rho_x\}),

where the maximisation is over input distributions (with the signal alphabet fixed). Block codes of length n achieve rate \chi with vanishing error as n \to \infty.

In other words: the Holevo quantity is not just an upper bound on mutual information — it is achievable at large block length, just like Shannon's capacity for classical channels. The two bookends (Shannon for classical, HSW for quantum) have the same structure: capacity = max mutual information across input distributions. See the HSW theorem chapter for the full story.

Worked examples

Common confusions

• "The Holevo bound says quantum computers can't beat classical." No. Holevo bounds information transmission, not computation. A quantum computer that produces a 100-bit output still compresses an enormous computational process into 100 qubits of output, and the Holevo bound just says the output itself conveys at most 100 bits when measured. The speedup in algorithms like Shor's or Grover's is in the number of gates used to prepare that output, not in the bits-per-qubit of the output itself.

• "Superdense coding violates the Holevo bound." It does not. Superdense coding consumes a pre-shared Bell pair, which is a separate quantum resource. The Holevo bound applies to the transmitted qubit alone, which is in the maximally mixed state I/2 with \chi = 1 bit. The second bit of classical information comes from the ebit of entanglement, not from the transmitted qubit. The bound is resource-faithful.

• "\chi equals I(X; Y) always." No — \chi \geq I(X; Y). The Holevo quantity is the maximum over measurements; most measurements leave slack. HSW says this slack closes in the block-coding limit, but for a single-shot measurement, I(X; Y) can be strictly less than \chi.

• "The Holevo bound requires the ensemble to be pure-state." No. The full bound \chi = S(\rho) - \sum_x p(x) S(\rho_x) applies to arbitrary mixed-state ensembles. For pure-state ensembles the second term vanishes, giving the cleaner \chi = S(\rho). Both forms are correct in their respective settings.

• "The Holevo bound is about information from a single measurement." No — the bound applies to any POVM, including adaptive and collective measurements. Collective measurements on n copies can achieve rates close to \chi, but individual measurements on single copies often cannot. The HSW theorem formalises "collective \Rightarrow rate \chi is achievable."

• "A quantum state encodes infinite classical information." In principle, yes — two real numbers on the Bloch sphere are a continuum. But you cannot extract more than \log_2 d = 1 classical bit per qubit via measurement. The infinity in the description and the finite extractable content are reconciled by the Holevo bound.

Going deeper

Accessible information vs Holevo quantity

For single-shot measurements, the supremum of I(X; Y) over all POVMs is the accessible information I_{\text{acc}}(\mathcal{E}) of the ensemble \mathcal{E} = \{p(x), \rho_x\}:

Holevo's bound says I_{\text{acc}} \leq \chi. In general the inequality is strict — computing I_{\text{acc}} exactly is NP-hard even for small ensembles. For the two-pure-state example above with overlap c, a known closed form exists (the Helstrom-measurement result), but for three or more states, numerical optimisation is usually required. The HSW theorem shows I_{\text{acc}}^{(n)} \to n \chi as n \to \infty (i.e., block coding closes the gap asymptotically), but finite-n results can be substantially below n\chi.

Pretty-good measurement (square-root measurement)

A canonical near-optimal POVM is the pretty-good measurement (PGM), also called the square-root measurement: M_x = \rho^{-1/2} p(x) \rho_x \rho^{-1/2} (with appropriate care for singular \rho). Hausladen and Wootters (1994) showed PGM achieves mutual information within a factor 2 of the optimum, and in many cases is exactly optimal. PGM is the central technical tool in the achievability proof of HSW — it is the measurement whose performance, amplified by block coding, converges to \chi.

The Holevo capacity of a noisy channel

For a general quantum channel \mathcal{N}: A \to B (not classical-quantum), the product-state classical capacity is

The HSW theorem says block codes using product input states achieve \chi(\mathcal{N}). Whether entangled input states can do better — the additivity question for classical capacity — was open for a decade until Hastings (2009) resolved it: surprisingly, entangled inputs can boost capacity for some channels, so the single-letter \chi is not always the capacity. The full capacity is \lim_{n \to \infty} \tfrac{1}{n} \chi(\mathcal{N}^{\otimes n}), the regularized Holevo quantity. The HSW theorem chapter treats this in depth.

Holevo's 1973 and the Indian connection

Alexander Holevo's 1973 paper "Some estimates for the amount of information transmissible by a quantum communication channel" [1] was published in Russian in Problems of Information Transmission — a Soviet journal then largely inaccessible to Western information theorists. The paper sat mostly unread for decades. It was only after Hausladen, Jozsa, Schumacher, Westmoreland and Wootters' 1996 rediscovery and proof of the capacity theorem that Holevo's original work was translated and properly credited. The Indian Statistical Institute (Kolkata) played a role in this rediscovery: K. R. Parthasarathy's 1992 book An Introduction to Quantum Stochastic Calculus gave the first English-language treatment of Holevo's bound accessible to a wider audience, and Parthasarathy's school at ISI Delhi has continued to produce influential work on quantum information — including the early rigorous proofs of the HSW theorem's Russian-school antecedents.

Refinements — continuity and strong converse

The modern form of Holevo's bound includes:

• Fannes-type continuity bounds: if two density operators are close in trace distance, their Holevo quantities differ by a quantifiable amount.
• Strong converse: for rates above \chi(\mathcal{N}), the block error probability approaches 1 (not just "bounded away from 0"). Wilde (2013) and others have proved strong converses for many classical-quantum channels.
• Second-order asymptotics: the finite-n gap between achievable rate and \chi scales as \sqrt{V/n} \cdot Q^{-1}(\epsilon) where V is a quantum-information variance and Q^{-1} is the Gaussian inverse CDF — directly paralleling Strassen's finite-blocklength corrections for classical channels.

Where this leads next

• Superdense coding — the protocol that reaches 2 classical bits per qubit using pre-shared entanglement; the companion piece to this chapter's Holevo-bound limits.
• HSW theorem — the achievability counterpart: the Holevo quantity is the classical capacity of a classical-quantum channel.
• Von Neumann entropy — the prerequisite S(\rho) whose appearance in \chi this chapter justifies.
• Quantum channel capacities — the full zoo of capacity measures: classical, private, quantum, and entanglement-assisted.
• Joint and conditional entropy — the quantum mutual-information formalism behind the proof sketch.
• Schumacher compression — the complementary theorem: how many qubits encode a quantum source.

References

1. Alexander S. Holevo, Some estimates for the amount of information transmissible by a quantum communication channel (1973) — Problems of Information Transmission. The original bound.
2. Paul Hausladen, Richard Jozsa, Benjamin Schumacher, Michael Westmoreland, William Wootters, Classical information capacity of a quantum channel (1996) — Phys. Rev. A 54, 1869. Rediscovery and achievability.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §12.1 (The Holevo bound) — Cambridge University Press.
4. John Preskill, Lecture Notes on Quantum Computation, Ch. 10 (Quantum Shannon theory) — theory.caltech.edu/~preskill/ph229. Clean proof via strong subadditivity.
5. Mark M. Wilde, Quantum Information Theory (2nd ed., 2017), Ch. 10–11 — arXiv:1106.1445. Modern treatment with strong converse.
6. Wikipedia, Holevo's theorem — compact statement, proof sketch, and reconciliation with superdense coding.