Quantum Compression

Our source emits \(\ket{\psi_\pm}=(\sqrt3\ket0\pm\ket1)/2\), each with probability \(1/2\). What does a receiver who does not know the signs hold? The off-diagonal entries of the two projectors cancel in the average, leaving

\[\rho=\tfrac12\ket{\psi_+}\bra{\psi_+}+\tfrac12\ket{\psi_-}\bra{\psi_-}=\mathrm{diag}(3/4,1/4).\]

Its entropy is \(S(\rho)=h_2(1/4)\approx0.811\). For \(n\) independent uses the block's average state is \(\rho\otimes\rho\otimes\cdots\otimes\rho\), written \(\rho^{\otimes n}\).

Could Alice simply measure each signal and compress the classical results? Measuring the eigenbasis of \(\rho\), here Z, gives 0 and 1 with probabilities \(3/4\) and \(1/4\), which classical compression could store in about 0.811 bits per signal. But the source never emits \(\ket0\) or \(\ket1\). The measurement replaces each signal by an eigenvector, so it changes the very states we were asked to keep. And measuring to learn the sign fails too, because the two signals are nonorthogonal. A quantum compressor must store the signals without reading them.

How should we score a compressor that is not perfect? When we studied copying we used the fidelity \(F=\bra\psi\sigma\ket\psi\), the probability that a recovered state \(\sigma\) passes the test for the intended pure state \(\psi\). It is 1 for exact recovery. For a source we average it over the signals. Some authors use the square root of this number instead, so the convention must be stated. There is also a general fidelity between two mixed states, due to Uhlmann, which we do not need here.

Score the measure-and-resend scheme. On \(\ket{\psi_+}\), measuring Z and preparing the result gives \(\ket0\) with probability \(3/4\) and \(\ket1\) with probability \(1/4\), so \(\sigma=\mathrm{diag}(3/4,1/4)\). Its fidelity is \(\bra{\psi_+}\sigma\ket{\psi_+}=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14=5/8\). The same holds for \(\ket{\psi_-}\).

Yet this scheme leaves the average state exactly as it was. So preserving \(\rho\) is far too weak a criterion: a compressor could pass it while losing the signals. A stronger test asks the compressor to preserve entanglement between the source and a reference system that never passes through it. Any scheme that secretly measures the signals fails that test.

What are the eigenvectors of \(\rho^{\otimes n}\)? Let \(\rho\ket j=\lambda_j\ket j\). A tensor product acts on each factor separately, so

\[\rho^{\otimes n}\ket{j_1j_2\cdots j_n}=\lambda_{j_1}\lambda_{j_2}\cdots\lambda_{j_n}\ket{j_1j_2\cdots j_n}.\]

The eigenvectors are strings of single-signal eigenvectors, and each eigenvalue is a product, exactly like the probability of a string from an independent classical source with probabilities \(\lambda_j\). So the classical counting applies unchanged. Strings with about \(n\lambda_j\) copies of each label \(j\) are typical. Each has eigenvalue about \(2^{-nS(\rho)}\). Since the eigenvalues add to one, there are at most about \(2^{n(S+\delta)}\) of them, for any small margin \(\delta>0\).

The span of the typical eigenvector strings is the typical subspace. Its total weight, the sum of their eigenvalues, is the probability that an eigenbasis measurement would find a typical string. By the law of large numbers, which needs the independent-use assumption, this weight tends to one as \(n\) grows. For \(n=3\), with "typical" taken to mean at most one 1, it is \(54/64\approx0.84\), still far from one.

How can Alice store a block in the typical subspace without learning which string it is in? Take the illustrative three-signal subspace spanned by \(000,001,010,100\). A coherent encoder sends these four to the two-qubit labels \(00,01,10,11\), and acts linearly on superpositions. For instance, \((\ket{000}+\ket{100})/\sqrt2\) becomes \((\ket{00}+\ket{11})/\sqrt2\), with no record of which term was which. A map that keeps inner products like this, from a subspace into a register, is an isometry. The decoder reverses it.

What about the part of the block outside the subspace? Alice may perform the two-outcome projective measurement "typical or not". It reveals only that, and leaves any superposition within the typical subspace intact. On "not", she sends some fixed state and accepts a failure.

How much fidelity does this cost? Let \(P\) be the projector onto the typical subspace, and suppose a block signal \(\ket\psi\) has \(\bra\psi P\ket\psi=1-\epsilon_\psi\). The "typical" branch occurs with probability \(\|P\ket\psi\|^2\) and recovers \(P\ket\psi/\|P\ket\psi\|\), whose fidelity with \(\ket\psi\) is \(|\bra\psi P\ket\psi|^2/\|P\ket\psi\|^2\). Multiplying, the fidelity is at least \((1-\epsilon_\psi)^2\geq1-2\epsilon_\psi\). Averaged over the source, the \(\epsilon_\psi\) average to the weight outside the typical subspace. So the average fidelity is at least one minus twice the discarded weight.

For our three-signal toy subspace the discarded weight is \(10/64\), so the bound guarantees only about \(0.69\). This small example shows the map and its finite loss. It does not show that three signals reach the entropy rate.

A register of \(m\) qubits has \(2^m\) orthogonal labels. So a subspace of dimension \(D\) fits into \(m=\lceil\log_2D\rceil\) qubits, where the ceiling rounds up to the next whole number. The typical subspace has \(D\leq2^{n(S+\delta)}\), so \(m\leq\lceil n(S+\delta)\rceil\). Per signal, the rate is at most \(S+\delta+1/n\), and the rounding cost \(1/n\) vanishes for long blocks. Since \(\delta\) can be as small as we like, any rate above \(S\) is reachable with fidelity tending to one.

Can a different scheme go below \(S\)? We quote Schumacher's quantum coding theorem (1995), which includes the converse. For a memoryless source of finite-dimensional signals, with fidelity required to tend to one, the entropy \(S(\rho)\) is the optimal rate in qubits per signal. Rates above it are achievable, and rates below it are not. The typical-subspace construction is the achievability half; the converse needs an argument we do not give. For our source the limiting rate is about 0.811 qubits per signal.

What exactly does the theorem promise for our source? A rate of 0.85 qubits per signal lies above the entropy, so long enough blocks can be compressed at that rate with fidelity as close to one as we like. A rate of 0.75 lies below it, and no scheme can keep fidelity near one. A single small encoding that happens to work proves neither statement.

The promise is asymptotic. It does not say that three signals fit faithfully into \(3\times0.811\approx2.433\) qubits. A register has a whole number of qubits, finite blocks leave atypical weight behind, and real encoding circuits have costs.

The assumptions matter too. If the source has memory, if its ensemble is unknown, or if every possible input must be preserved exactly rather than typical source behaviour, the theorem does not apply unchanged. And a compressible source does not mean that an arbitrary quantum computation can safely discard most of its qubits.

Many copies of a mixed state have a small typical subspace. Many copies of a weakly entangled pair have one too. Could Alice and Bob turn many weakly entangled pairs into fewer perfect Bell pairs?

Sources and further study: Schumacher, Quantum coding.