Schumacher Compression

Shannon's 1948 theorem says: a classical source with entropy H(X) bits per symbol can be compressed to nH(X) bits per n-symbol block, and no further. That number H(X) is the information content of the source — not by decree, but because compression proves it.

Forty-seven years later, Benjamin Schumacher asked the same question for quantum sources. Can a quantum source that emits states with density operator \rho be compressed? If so, to what rate? The answer is elegant and exact: the rate is S(\rho) qubits per symbol, where S(\rho) = -\text{tr}(\rho\log\rho) is the von Neumann entropy. This theorem, now the founding result of quantum information theory, is why we measure quantum information in qubits and why the von Neumann entropy is the right measure of a quantum source's content.

This chapter builds the picture before the algebra. You will see a quantum source emitting copies of a state, a high-dimensional Hilbert space the copies live in, a lower-dimensional "typical" subspace inside it, and a compression protocol that projects onto the typical subspace and throws the rest away. The shocking fact — shocking because it parallels Shannon's classical theorem so cleanly — is that this works, asymptotically, with fidelity arbitrarily close to 1.

The classical warm-up — Shannon in three sentences

You have a source emitting independent symbols X_1, X_2, \ldots, X_n from a distribution p over an alphabet \mathcal{X}. The typical set A_\epsilon^{(n)} is the set of sequences (x_1, \ldots, x_n) whose empirical probability is close to 2^{-nH(X)}. As n \to \infty: there are \approx 2^{nH(X)} typical sequences; each has probability \approx 2^{-nH(X)}; they collectively carry almost all the probability mass. Shannon's source-coding theorem then says you can compress the source to nH(X) bits per block by indexing the typical sequences and accepting a vanishing error on the atypical rest. See the Shannon entropy recap chapter for the formal statement.

Now replace every classical word in that paragraph with its quantum counterpart: probability distribution \to density operator, sequence \to tensor-product state vector, typical set \to typical subspace, H(X) \to S(\rho). That is Schumacher's theorem.

Schumacher's theorem — the statement

Reading the statement. The achievability clause says you can do it at any rate above S(\rho). The converse clause says you cannot do it below S(\rho). The two together make S(\rho) a sharp threshold — exactly the kind of theorem Shannon's original is, applied now to density operators instead of distributions. The compression map \mathcal{C} and decompression map \mathcal{D} are completely-positive trace-preserving (CPTP) maps; the "fidelity" is the overlap between the original and the recovered state, measured as F(\rho, \sigma) = \left(\text{tr}\sqrt{\sqrt\rho \sigma \sqrt\rho}\right)^2 or the simpler pure-state fidelity when applicable.

Why S(\rho) and not \log_2 d: the dimension d counts possible states, not probable ones. A state ρ with eigenvalues (0.9, 0.05, 0.05) lives nominally in d = 3, but its entropy is much less than \log_2 3 = 1.585 — the probability mass hugs one eigenvector. The compression rate has to be S(\rho) because that is the number of qubits a "long stretch" of the source actually deserves. Atypical configurations get thrown away with vanishing penalty, just as in the classical case.

Typical subspace — the quantum picture

The whole theorem rests on a single construction: the typical subspace. It is the quantum analogue of Shannon's typical set, and defining it is most of the work.

The ingredients

Start with the spectral decomposition of \rho:

where \{|x\rangle\} is an orthonormal eigenbasis and \{p(x)\} is the eigenvalue distribution. Each eigenvalue is a probability: p(x) \geq 0 and \sum_x p(x) = 1.

Now take n copies:

where the ket |x_1 x_2 \cdots x_n\rangle = |x_1\rangle \otimes |x_2\rangle \otimes \cdots \otimes |x_n\rangle is an eigenvector of \rho^{\otimes n} with eigenvalue p(x_1)p(x_2)\cdots p(x_n).

So \rho^{\otimes n} is diagonal in the product basis \{|x_1 \cdots x_n\rangle\}, and the eigenvalues are products of n classical probabilities. This is where the quantum problem reduces to a classical one.

Reading the definition. The typical subspace is spanned by those tensor-product eigenvectors whose eigenvalue p(x_1)\cdots p(x_n) is near 2^{-nS(\rho)} — i.e., whose index string is classically typical for the eigenvalue distribution. Everything atypical is discarded. The projector \Pi_\epsilon^{(n)} is the quantum gate that projects onto this subspace.

Three properties — the quantum AEP

The typical subspace satisfies three properties, which together form the quantum asymptotic equipartition property (AEP):

1. Dimension. \dim \mathcal{T}_\epsilon^{(n)} \leq 2^{n(S(\rho) + \epsilon)}, and for large n is bounded below by (1 - \delta)\,2^{n(S(\rho) - \epsilon)}. Asymptotically, \log_2 \dim \mathcal{T}_\epsilon^{(n)} \approx nS(\rho).

2. Weight. \text{tr}(\Pi_\epsilon^{(n)} \rho^{\otimes n}) \to 1 as n \to \infty. Almost all the probability weight of \rho^{\otimes n} lives in the typical subspace.

3. Uniformity. For any typical basis vector |x_1 \cdots x_n\rangle \in \mathcal{T}_\epsilon^{(n)}, the eigenvalue satisfies 2^{-n(S(\rho)+\epsilon)} \leq p(x_1)\cdots p(x_n) \leq 2^{-n(S(\rho)-\epsilon)}. The state \rho^{\otimes n}, restricted to the typical subspace, looks approximately maximally mixed on a 2^{nS(\rho)}-dimensional space.

Why these three properties follow from the classical AEP: since \rho^{\otimes n} is diagonal in the product basis, the eigenvalue distribution \{p(x_1)\cdots p(x_n)\} is exactly the joint classical distribution of n i.i.d. draws from p. Every classical statement about the typical set translates to a statement about typical eigenvectors. The quantum AEP is the classical AEP of \rho's spectrum.

The compression protocol

You now have everything you need to state the protocol.

The encoder

Alice holds n copies of \rho as the joint state \rho^{\otimes n} on \mathcal{H}^{\otimes n}. She wants to send it to Bob using the smallest possible quantum register.

1. Project onto the typical subspace. Apply the projector \Pi_\epsilon^{(n)} to \rho^{\otimes n}. Outcome "typical" occurs with probability \text{tr}(\Pi_\epsilon^{(n)} \rho^{\otimes n}) \geq 1 - \epsilon; outcome "atypical" with probability \leq \epsilon. If atypical, Alice substitutes an arbitrary fixed state inside \mathcal{T}_\epsilon^{(n)} (this is a one-in-\epsilon-chance failure; it costs a small fidelity loss in exchange for a clean protocol).
2. Represent the state inside the typical subspace as a quantum index. Fix an isometry V : \mathcal{T}_\epsilon^{(n)} \hookrightarrow (\mathbb{C}^2)^{\otimes \lceil nS(\rho) \rceil}. This is always possible because the target register has dimension 2^{\lceil nS(\rho) + \epsilon' \rceil} \geq \dim \mathcal{T}_\epsilon^{(n)}.
3. Send the \lceil nS(\rho) \rceil-qubit register to Bob.

The decoder

Bob receives the quantum register.

1. Apply the inverse isometry V^\dagger to re-embed the state into \mathcal{T}_\epsilon^{(n)} \subset \mathcal{H}^{\otimes n}.
2. Output the embedded state.

Fidelity analysis in three lines

The encoder output is \Pi_\epsilon^{(n)} \rho^{\otimes n} \Pi_\epsilon^{(n)} (up to a very-small-probability failure branch). The decoder returns this state unchanged into the larger Hilbert space. The fidelity with the original \rho^{\otimes n} is at least

by the "weight" property of the typical projector. Why this inequality follows: the projected state agrees with the original on the typical subspace (the projector is the identity there) and returns zero on the orthogonal complement. The overlap is exactly the fraction of weight of \rho^{\otimes n} inside the typical subspace, which is \text{tr}(\Pi_\epsilon^{(n)} \rho^{\otimes n}). That quantity is \geq 1 - \epsilon by the weight property.

As n \to \infty with \epsilon \to 0, fidelity \to 1 and the rate \to S(\rho). Achievability is proved.

The converse — why you cannot do better

Suppose, for contradiction, that you could compress at rate R < S(\rho) with non-vanishing fidelity. Your compressed space has dimension \leq 2^{nR} < 2^{n(S(\rho) - \delta)} for some \delta > 0. But the typical subspace of \rho^{\otimes n} has dimension \geq (1 - \text{small})\,2^{n(S(\rho) - \epsilon/2)} and carries almost all the weight. The compressor's subspace is exponentially smaller. By a pigeon-hole argument on Hilbert-space overlaps, the compressor must discard a non-vanishing fraction of the typical subspace's vectors, causing fidelity to drop below any fixed threshold.

The full proof uses Fannes' inequality and the continuity of entropy to tighten this to a quantitative bound; Preskill's Chapter 10 [2] spells it out. The qualitative picture above is the engineering reason: below S(\rho) qubits, there is not enough room in the compressed register to preserve the typical-subspace dimension, and fidelity must fail.

Operational meaning — qubits, not bits

Schumacher's theorem is the reason quantum information is measured in qubits. Before 1995, one could argue for "quantum bits" as a name, a nod to classical bits, but there was no theorem anchoring the word. With Schumacher: a quantum source with entropy S bits per symbol compresses to nS qubits per n-symbol block — not nS bits, because the result lives in a Hilbert space of dimension 2^{nS}, and a qubit is precisely a dimension-2 piece of a Hilbert space. The unit matches the resource.

Comparison with classical compression

The two theorems are mathematically the same argument applied to two different linear-algebraic settings: scalars for Shannon, operators for Schumacher. The eigenvalues of \rho carry all the entropy, so compressing the quantum source reduces exactly to compressing the classical distribution of its eigenvalues.

A subtlety — non-commuting ensembles

There is one place the quantum story gets genuinely richer than the classical. Suppose the source emits not always the same density operator \rho, but a sequence drawn from an ensemble \{p_i, |\psi_i\rangle\} — state |\psi_i\rangle with probability p_i. The average state is \rho = \sum_i p_i |\psi_i\rangle\langle\psi_i|. Schumacher's theorem still applies: the compression rate is S(\rho). But each |\psi_i\rangle is a pure state with entropy 0; the entropy comes entirely from the classical mixing \{p_i\} and from the fact that the pure states may be non-orthogonal. If the |\psi_i\rangle were mutually orthogonal, S(\rho) = H(p) (Shannon entropy of the mixing weights). If they are non-orthogonal, S(\rho) < H(p) — the quantum compression is tighter than any classical scheme that naïvely indexed the states. This is where quantum information genuinely beats classical, and it leads directly into the Holevo bound in the next chapter.

Worked examples

Common confusions

• "Schumacher compression requires the decoder to know \rho." Yes, it does. Like all rate-distortion and source-coding theorems, Schumacher's is an asymptotic existence theorem: it assumes encoder and decoder agree on \rho in advance and build a codebook tuned to it. If \rho is unknown, you need a universal compression scheme (Jozsa-Horodecki 1998 extended Schumacher to this case with a small rate penalty).

• "The typical subspace is a specific, canonical subspace." It depends on \epsilon and on \rho. For a given \rho, varying \epsilon gives a family of nested subspaces — smaller \epsilon gives a smaller subspace with more weight outside; larger \epsilon gives a larger subspace with more weight inside. In the limit \epsilon \to 0 with n \to \infty tuned appropriately, the rate approaches S(\rho) and the fidelity approaches 1.

• "Compression works on a single copy." It does not. Schumacher's theorem is about n \to \infty. For n = 1, the typical-subspace structure degenerates: a single copy of a mixed state cannot be compressed to fewer qubits without fidelity loss. The theorem becomes exact only as a rate, averaged over long blocks.

• "The qubit is just a bit with extra structure." The whole point of Schumacher is the opposite: a qubit is not a bit. Compression rates differ (a maximally mixed source has classical entropy \log_2 d bits but quantum compression rate \log_2 d qubits; non-orthogonal pure-state ensembles have Shannon entropies of their mixing weights that can exceed S(\rho) — the quantum rate is strictly smaller). The qubit earns its name because Schumacher's theorem picks it as the native resource unit.

• "Schumacher compression is lossless." It is asymptotically lossless: fidelity \to 1 as n \to \infty. For any finite n, there is a small but positive probability that the state is atypical and the compressor's approximation loses fidelity. This is exactly analogous to Shannon's theorem: both achieve vanishing error rather than zero error.

• "You can beat Schumacher using entanglement-assisted or classical-assisted compression." For i.i.d. quantum sources without side information, no — Schumacher's rate S(\rho) is optimal. Pre-shared entanglement or classical side information can help in more elaborate compression settings (Slepian-Wolf analogues, CQ coding), but for the basic source-coding problem, S(\rho) is the ultimate bound.

Going deeper

Fannes' inequality and the continuity argument

The converse to Schumacher's theorem relies on Fannes' inequality: for density operators \rho, \sigma on a d-dimensional space with trace distance T(\rho, \sigma) \leq \eta < 1/e,

Applied to the compressed state \sigma = \mathcal{D} \circ \mathcal{C}(\rho^{\otimes n}) and the original \rho^{\otimes n}, if the trace distance is small then the entropies must be close. But the entropy of the compressed state is bounded by the log of the compressed-register dimension: S(\sigma) \leq nR. If R < S(\rho) = \tfrac{1}{n}S(\rho^{\otimes n}), Fannes' inequality forces the trace distance to grow, giving the desired fidelity bound. Preskill's Chapter 10 [2] and Nielsen–Chuang §12.2 [3] give the argument in full.

Universal compression — unknown \rho

Schumacher's original protocol requires encoder and decoder to know \rho in advance (to construct \Pi_\epsilon^{(n)}). Jozsa and collaborators (1998) extended this to the universal setting: a single compressor that works for any \rho in a given class, with an asymptotic rate penalty that vanishes as n \to \infty. Modern universal quantum compression uses group-representation-theoretic machinery — Schur-Weyl duality — to symmetrise over unknown eigenbases while preserving typicality. The rate is still S(\rho), but now \rho can be learned from the block itself via a measurement of its type.

Mixed-state ensembles and the Holevo gap

If the source emits |\psi_i\rangle with probability p_i, Alice's choice variable has classical entropy H(\{p_i\}). The average state has von Neumann entropy S(\rho) \leq H(\{p_i\}), with equality iff the |\psi_i\rangle are mutually orthogonal. The gap

for pure-state ensembles, is the Holevo quantity \chi. For mixed-state ensembles it becomes S(\rho) - \sum_i p_i S(\rho_i). The Holevo bound says \chi is the maximum classical information extractable from the ensemble via any measurement. Schumacher compression and the Holevo bound are therefore two sides of the same coin: Schumacher says the qubit rate is S(\rho); Holevo says the classical-bit rate extractable is \chi \leq S(\rho). They agree for pure-state ensembles. The Holevo bound chapter develops this story.

Reliability exponents and finite-n corrections

For finite n, Schumacher's theorem gives rate S(\rho) + O(\log n / n) with fidelity 1 - e^{-n E(R)}, where E(R) is the reliability exponent — a Cramér-type large-deviations rate governing how fast fidelity approaches 1 as a function of rate margin R - S(\rho). The quantum reliability exponent equals the classical Cramér exponent of the eigenvalue distribution, another instance of the "quantum source coding reduces to classical source coding of eigenvalues" principle. Hayashi's Quantum Information Theory [5] gives a complete treatment.

An Indian connection — Harish-Chandra at TIFR

The mathematical machinery behind universal quantum compression — Schur-Weyl duality, representations of the symmetric and unitary groups — was significantly advanced by Harish-Chandra during his years at the Tata Institute of Fundamental Research in Mumbai before moving to Princeton. His work on the representation theory of semisimple Lie groups is the foundation on which modern universal quantum compressors (Hayashi–Matsumoto 2002, Christandl et al. 2007) are built. The state-of-the-art proofs of universal Schumacher compression route through Harish-Chandra's characters and the Gelfand-Tsetlin basis — Indian mathematical contributions sitting squarely inside a cornerstone result of quantum information theory.

Where this leads next

• Holevo bound — the companion theorem: how much classical information can be extracted from a quantum source. Answers the question Schumacher leaves open about non-orthogonal ensembles.
• Von Neumann entropy — the prerequisite object S(\rho) whose operational meaning Schumacher pins down.
• HSW theorem — the Holevo–Schumacher–Westmoreland theorem, giving the classical capacity of a quantum channel. The direct successor to both this chapter and the Holevo bound.
• Quantum channel capacities — the full zoo of capacity measures (classical, private, quantum, entanglement-assisted) and how they relate.
• Shannon entropy recap — the classical parent theorem, whose proof structure Schumacher directly mimics.
• Density operator — the mathematical object on which both \rho and \rho^{\otimes n} are built.

References

1. Benjamin Schumacher, Quantum coding (1995) — Phys. Rev. A 51, 2738. The founding paper; introduces the term "qubit" and proves the source-coding theorem.
2. John Preskill, Lecture Notes on Quantum Computation, Ch. 10 (Quantum Shannon theory) — theory.caltech.edu/~preskill/ph229. Full proof of Schumacher's theorem with the typical-subspace construction.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §12.2 (Quantum data compression) — Cambridge University Press.
4. Richard Jozsa and Benjamin Schumacher, A new proof of the quantum noiseless coding theorem (1994) — J. Mod. Opt. 41, 2343. Simplified proof and universal-compression extension.
5. Masahito Hayashi, Quantum Information Theory: Mathematical Foundation (2nd ed., 2017) — Springer. Reliability exponents and universal compression rates.
6. Wikipedia, Typical subspace — compact statement and properties.