The Exercise

A source emits, at each use, one of the pure states $|\psi_j\rangle$ of a quantum system $Q$, the state $|\psi_j\rangle$ with probability $p_j$, independently from one use to the next. Fix a rate $R$ above the von Neumann entropy of the source’s density operator. The exercise asks for an operation on $n$ copies of $Q$ that puts every output into a subspace of dimension at most $e^{nR}$ and returns the strings of $n$ states the source emits with an ensemble average fidelity tending to one as $n$ grows. This is Schumacher’s quantum data compression, with its reliability judged by the ensemble average fidelity.

A Source of Pure States

A quantum system $Q$ has as its state space a finite dimensional complex Hilbert space.^✦ A state $\rho$ of $Q$ is a positive operator of unit trace on the state space of $Q$.^✦ A pure state $|\psi\rangle$ of $Q$ is a unit vector in the state space of $Q$^✦; it determines the state $|\psi\rangle\langle\psi|$, the projector onto that vector.^✦

The composite system $\bigotimes_i Q_i$ of finitely many systems $Q_i$ is the system whose state space is the tensor product of their state spaces^✦, and the tensor power $Q^{\otimes n}$ is the composite of $n$ copies of $Q$.^✦ The product of pure states $|\psi_i\rangle$, one of each $Q_i$, is the pure state $\bigotimes_i |\psi_i\rangle$ of the composite.^✦

An ensemble $\{p_j, |\psi_j\rangle\}$ of pure states of $Q$ is a finite family of pure states $|\psi_j\rangle$ of $Q$ with weights $p_j \ge 0$ that sum to one.^✦ The density operator of the ensemble is the state $$\rho = \sum_j p_j\, |\psi_j\rangle\langle\psi_j| .$$(1)^✦

The von Neumann entropy of a state $\rho$ of $Q$ is $$S(\rho) = -\operatorname{tr}(\rho \log \rho),$$(2)^✦ the Shannon entropy of its eigenvalues, measured in nats.

The ensemble of $n$ uses of $\{p_j, |\psi_j\rangle\}$ is the ensemble of pure states of $Q^{\otimes n}$ labelled by the sequences $J = (j_1, \dots, j_n)$, with weights and states $$p_J = p_{j_1} \cdots p_{j_n}, \qquad |\psi_J\rangle = |\psi_{j_1}\rangle \otimes \cdots \otimes |\psi_{j_n}\rangle .$$(3)^✦

Channels, Measurements and Fidelity

A quantum channel $\mathcal{E}$ on $Q$ is a completely positive, trace preserving linear map on the operators of the state space of $Q$, acting on the states of $Q$.^✦

A measurement on $Q$ with a finite set of outcomes is a family of measurement operators $M_m$ on the state space of $Q$, one for each outcome $m$, satisfying the completeness relation $\sum_m M_m^\dagger M_m = I$.^✦ The positive operator valued measure (POVM) of the measurement has the effects $E_m = M_m^\dagger M_m$^✦, and the probability of the outcome $m$ on a state $\rho$ is given by the Born rule, $$p(m) = \operatorname{tr}\bigl(M_m \rho M_m^\dagger\bigr) = \operatorname{tr}(E_m \rho).$$(4)^✦

The fidelity of two states $\rho$ and $\sigma$ of $Q$ is the nonnegative number $$F(\rho, \sigma) = \operatorname{tr} \sqrt{\sqrt{\rho}\, \sigma \sqrt{\rho}} .$$(5)^✦ For a source that emits the state $\rho_j$ with probability $p_j$, the ensemble average fidelity of a map $\mathcal{E}$ on the states of $Q$ is $$\bar F = \sum_j p_j\, F\bigl(\rho_j, \mathcal{E}(\rho_j)\bigr)^2 .$$(6)^✦

The Typical Subspace

The spectrum of a state $\rho$ of $Q$ is the list $\lambda_1, \dots, \lambda_d$ of its eigenvalues, repeated with multiplicity, where $d$ is the dimension of the state space of $Q$ and $\rho|e_k\rangle = \lambda_k |e_k\rangle$ for an orthonormal eigenbasis $|e_1\rangle, \dots, |e_d\rangle$ of $\rho$.^✦ The $\lambda_k$ are nonnegative and sum to one, so $\lambda$ is a probability distribution on the labels $k$.

The product eigenbasis of $\rho$ on $Q^{\otimes n}$ is the orthonormal basis of the state space of $Q^{\otimes n}$ formed by the vectors $$|e_K\rangle = |e_{k_1}\rangle \otimes \cdots \otimes |e_{k_n}\rangle, \qquad K = (k_1, \dots, k_n).$$(7)^✦

Fix a tolerance $\epsilon > 0$. A sequence $K = (k_1, \dots, k_n)$ of labels is typical at tolerance $\epsilon$ when, for $n$ independent draws from the distribution $\lambda$, its probability $\lambda_{k_1} \cdots \lambda_{k_n}$ satisfies $\bigl| -\tfrac{1}{n} \log(\lambda_{k_1} \cdots \lambda_{k_n}) - S(\rho) \bigr| \le \epsilon$. The typical subspace $T(n, \epsilon)$ is the span of the vectors (7) with $K$ typical, so its dimension is the number of typical sequences.^✦

An orthonormal basis $\{|b_\kappa\rangle\}$ of the state space of a system, with an outcome assigned to each index $\kappa$, defines a block measurement: its operator for the outcome $m$ is the orthogonal projector onto the span of the $|b_\kappa\rangle$ assigned $m$.^✦ The typical subspace measurement on $Q^{\otimes n}$ is the block measurement of the product eigenbasis (7) with two outcomes, one for the typical $K$ and one for the rest.^✦ Its operators are the projector $P(n, \epsilon)$ onto $T(n, \epsilon)$ and the projector $I - P(n, \epsilon)$ onto its orthogonal complement, and by (4) it finds a state $\sigma$ of $Q^{\otimes n}$ in the typical subspace with probability $\operatorname{tr}\bigl(P(n, \epsilon)\, \sigma\bigr)$.

The Claim

The channel $\mathcal{C}_n$ is the whole scheme, compression followed by decompression.

What Is Checked

The claim (8) is stated over an ensemble of pure states and its density operator (1), the von Neumann entropy (2), the ensemble of $n$ uses (3), quantum channels on $Q^{\otimes n}$, the number of typical sequences, the typical subspace measurement built on the product eigenbasis (7) with the probability (4) of its outcome, and the ensemble average fidelity (6) with the fidelity (5) inside it.

The library proves that the density operator (1) is a state, positive and of unit trace, since each $|\psi_j\rangle\langle\psi_j|$ has unit trace and the weights sum to one. It proves that a product of pure states is again a unit vector and that the weights $p_J$ of (3) are nonnegative and sum to one, so the ensemble of $n$ uses is an ensemble of pure states of $Q^{\otimes n}$. It also proves that the projectors of a block measurement satisfy the completeness relation, which makes the typical subspace measurement a measurement.