Holevo Bound

The Holevo bound is a theorem about how much classical information can be recovered from a quantum ensemble. Suppose a sender encodes one of M classical messages x into a quantum state rho_x with probability p_x, and a receiver applies any POVM measurement to the resulting mixed state rho = sum_x p_x rho_x. The mutual information I(X;Y) between the sent message X and the measurement outcome Y is bounded above by the Holevo chi quantity: chi = S(rho) - sum_x p_x S(rho_x), where S denotes von Neumann entropy. For n qubits, chi is at most n bits, regardless of how clever the encoding or measurement strategy is.

Superdense coding appears to violate this bound at first glance, since it transmits 2 bits of classical information using a single qubit. The resolution is that superdense coding relies on a pre-shared entangled pair, so the effective resource is one qubit of quantum communication plus one ebit of entanglement. When the entanglement is accounted for, the total quantum resource is two qubits, and the Holevo bound is respected: 2 bits from 2 qubits. Without entanglement, a single qubit carries at most 1 bit, confirming the bound. This is why the bound is stated per qubit of communication, not per qubit of encoding.

The Holevo bound connects directly to the quantum channel capacity. The classical capacity C of a quantum channel is given by the regularized Holevo information: C = lim (1/n) max chi(channel^n), where the maximum is over all input ensembles and the limit accounts for entangled input encodings. For many channels, the single-letter formula C = max chi suffices (the channel is “additively”), but some quantum channels have superadditive classical capacity, meaning entangled inputs across multiple channel uses exceed what single-use encoding can achieve. This superadditivity has no classical analog and was a major surprise when first demonstrated.

A common misconception is that quantum computers can solve NP-complete problems by encoding all possible inputs into a superposition and measuring once. The Holevo bound refutes this: even if a quantum computer prepares a superposition over exponentially many inputs and queries an oracle, any single measurement extracts at most n bits. The exponential information in the amplitudes is not all accessible; most of it is destroyed by the measurement process. This is why quantum speedups require careful algorithm design (interference, amplitude amplification) rather than brute-force parallelism, and why quantum computers are not generally believed to solve NP problems in polynomial time.