1. Quick check §
Compute the entropy of a source with eigenvalues (1/2,1/2).
Hint 1
Both log probabilities are one bit.
Worked solution
The entropy is one bit, so faithful blind compression has threshold one qubit per signal.
Quantum Information Theory · Chapter 05
Quantum Compression
How can we store a quantum source using fewer qubits while preserving its correlations?
In this chapter · 3 sections
Reading guide · preparation and approach
Starting point: Chapters 1–4; independent random variables and entropy.
Anchor example: A memoryless qubit source with average state diag(0.8,0.2).
Method: Count spectral strings by their probabilities, then encode their typical subspace coherently.
Watch for: Measuring the eigenbasis may preserve statistics while destroying the quantum message.
This lesson includes explanations, worked examples, and problems with solutions. Advanced results whose proofs are outside the chapter are identified explicitly.
5.1 Typical sequences
5.1.1 Probability concentrates, not individual outcomes
Let a source independently emit systems with average state \(\rho\). In its eigenbasis, \(\rho=\sum_i\lambda_i|i\rangle\langle i|\), and \(\rho^{\otimes n}\) has eigenvalues \(\lambda_{i_1}\cdots\lambda_{i_n}\). Define a string as \(\delta\)-typical if its negative log probability per symbol differs from \(S(\rho)\) by at most \(\delta\). The law of large numbers says the total probability of these strings tends to one. It does not say a particular typical string becomes likely.
Each typical string has probability between \(2^{-n(S+\delta)}\) and \(2^{-n(S-\delta)}\). Therefore the number of typical strings is at most \(2^{n(S+\delta)}\). If their total mass is at least \(1-\epsilon\), their number is at least \((1-\epsilon)2^{n(S-\delta)}\). These bounds are the bridge between entropy and storage dimension. The upper bound comes from the fact that probabilities sum to at most one; the lower bound uses the largest permitted probability per typical string.
For spectrum \((0.8,0.2)\), typical strings contain about \(0.2n\) occurrences of the second eigenvector. Their count grows at exponential rate \(h_2(0.2)\approx0.721928\). The entire Hilbert space has dimension \(2^n\), but almost all source weight occupies a much smaller spectral subspace. “Almost all” refers to this source distribution, not to all possible input states.
Worked check 5.1. What storage rate does the typical-subspace dimension suggest for this source?
Reasoned solution
Approximately 0.721928 qubits per signal asymptotically. For a rigorous construction choose a rate strictly above that entropy, then let the block size grow; the finite-block overhead cannot be dropped without analysis.
5.2 Coherent encoding
5.2.1 Preserve the reference, not only the density matrix
Let \(\Pi\) project onto the typical subspace, whose dimension fits in a memory of \(m\) qubits. An encoder maps that subspace isometrically into the memory. A decoder reverses the isometry. The atypical component can be mapped to a fixed fallback state to complete a trace-preserving channel. No measurement distinguishing the individual typical eigenvectors is needed. Their superpositions must remain coherent.
The appropriate error test introduces a purification \(|\psi\rangle_{RA}\) of the source state. Entanglement fidelity is \(F_e=\langle\psi|(\operatorname{id}_R\otimes\mathcal D\mathcal E)(|\psi\rangle\langle\psi|)|\psi\rangle\). It tests whether encoding and decoding preserve correlations with a reference. Simply checking \(\mathcal D\mathcal E(\rho)\approx\rho\) is insufficient: a device could throw away the input and prepare \(\rho\) anew, passing that weak test while losing every reference correlation.
For a compression channel with one Kraus operator equal to \(\Pi\) and all other branches acting on its complement, the identity \(F_e=\sum_k|\tr(\rho A_k)|^2\) gives \(F_e\ge[\tr(\rho\Pi)]^2\). If typical weight is at least \(1-\epsilon\), then fidelity is at least \((1-\epsilon)^2\). This direct estimate explains why high typical weight supports faithful quantum storage without inspecting the encoded information.
Worked check 5.2. Why does complete dephasing fail to compress a maximally mixed qubit faithfully even though it preserves I/2?
Reasoned solution
Purify I/2 with a Bell pair. Dephasing one half produces the equal mixture of |00⟩ and |11⟩, whose overlap with the Bell pair is 1/2. The reduced state passes, but entanglement fidelity does not.
5.3 The coding theorem and finite blocks
5.3.1 A rate statement needs a source model
Schumacher compression, stated here in its memoryless finite-dimensional form, says that a source with average state \(\rho\) can be compressed at any rate above \(S(\rho)\) qubits per signal with entanglement fidelity tending to one. Rates below the entropy cannot attain asymptotically faithful storage in this blind encoding model. The typical-subspace construction gives the achievability mechanism; the full converse is a theorem whose proof we do not reproduce. See Watrous, Chapter 5 for a precise source-coding treatment.
A small block makes the overhead tangible. With ten independent signals and second-eigenvector probability 0.2, keep strings containing at most three such symbols. Their subspace has dimension \(1+10+45+120=176\), requiring eight qubits. Its probability is \(\sum_{k=0}^3\binom{10}{k}0.2^k0.8^{10-k}\approx0.879126\). The simple fidelity lower bound is about 0.772863. An asymptotic rate near 0.722 therefore does not promise near-perfect storage in eight qubits for this block.
Correlated sources, unknown source states, and worst-case storage are different problems. If every state in a \(2^n\)-dimensional space must be preserved, no source bias is available to exploit. The next chapters change the resource from memory dimension to uses of a noisy transmission channel, where both encoding and decoding must combat environmental loss.
Worked check 5.3. If a source always emits a known pure state, how many asymptotic storage qubits are needed?
Reasoned solution
Zero per signal. The decoder can prepare the known state. Its source purification has no nontrivial reference correlation, unlike an unknown arbitrary pure input that must be preserved.
Summary
- Typicality turns entropy into a high-probability subspace dimension.
- Quantum compression must preserve coherence and reference correlations.
- The entropy rate is asymptotic; finite blocks require explicit dimension and fidelity calculations.
Questions and worked problems
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
2. Quick check §
What is the dimension of the full space for n qubits?
Hint 1
Multiply the local dimensions.
Worked solution
It is 2ⁿ, corresponding to n qubits of unrestricted memory.
3. Quick check §
If typical mass is 0.99, what fidelity lower bound follows?
Hint 1
Square the retained mass.
Worked solution
The bound is 0.9801; this is a lower bound, not necessarily the exact achieved fidelity.
4. Worked problem §
Count binary strings of length 6 with at most one 1.
Hint 1
Separate weights zero and one.
Worked solution
There are 1+6=7 strings. Their span fits in three qubits.
5. Worked problem §
For that length-6 subspace and p=0.2, compute retained probability.
Hint 1
Sum the zero- and one-error binomial probabilities.
Worked solution
The mass is 0.8⁶+6(0.2)(0.8⁵)=0.65536. The squared-mass fidelity bound is about 0.429497.
6. Worked problem §
Derive the upper bound on typical-subspace dimension.
Hint 1
Each typical eigenvalue is at least 2 to the power −n(S+δ).
Worked solution
If there are K typical strings, \(1\ge K2^{-n(S+\delta)}\), so \(K\le2^{n(S+\delta)}\).
7. Worked problem §
Show why keeping just the most probable individual string fails for p=0.2.
Hint 1
Calculate its block probability.
Worked solution
The all-zero string has probability 0.8ⁿ, tending to zero. High-probability storage requires many strings, not one representative.
8. Misconception §
Does preserving the average state imply preserving the source’s quantum information?
Hint 1
Consider discard-and-reprepare.
Worked solution
No. A replacement channel preserves that average state but destroys correlations with a purifying reference.
9. Misconception §
Can the i.i.d. formula be applied unchanged to an arbitrary correlated source?
Hint 1
Identify where tensor-product eigenvalues were used.
Worked solution
No. Independence supplied products of eigenvalues and a law-of-large-numbers argument. Correlated sources require an appropriate entropy-rate theorem and assumptions.
10. Extension §
Design a finite-block study of a biased binary source.
Hint 1
Sort weights by probability and record the retained mass.
Worked solution
For each n, choose a Hamming-weight cutoff, sum its binomial dimension and probability, and report ceiling(log₂ dimension) and squared retained mass. Plot memory rate against the certified fidelity bound; do not label the bound an exact optimum.