QUANTUM COMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 75

quantum decoder can the recover n photons with the original distribution (with
arbitrarily high fidelity for large n) from these compressed photons.

S CHUMACHER Q UANTUM N OISELESS C OMPRESSION . Schumacher [99] gave a
quantum noiseless coding theorem which provided asymptotically optimal noiseless
compression of a sequence of qubits independently sampled from a finite quantum
state ensemble (S, p). The quantum noiseless coding theorem states that for any
e , d 0 and sufficiently large n, (i) there is an n-to-n 0 quantum compression scheme

with fidelity at least 1 e and compression to length n 0 n ð H VN ðrÞþdÞ , and (ii)
any n-to-n 00 quantum compression scheme which gives compression to length
n 00 n ð H VN ðrÞdÞ , has fidelity

W

1 e . That is, in the limit of large code-block
size, the source's von Neumann entropy H VN ( r ) is asymptotically the number of
qubits per source state which is necessary and sufficient to encode the output of the
source with arbitrarily high fidelity. Given a known finite quantum state ensemble
(S, p), Schumacher's compression scheme assumes a known basis for which the
density matrix r is diagonal, with nonincreasing values along the diagonal.
The proof of the Schumacher quantum noiseless coding theorem and its
refinements by Jozsa and Schumacher [101] and H. Szeto [102] make use of the
existence of a typical subspace L (see [101]) within a Hilbert space of n qubits over
a source of von Neumann entropy H VN ( r ). The typical subspace L has dimension
2 nH VN ðrÞ and with high probability, a sample of n qubits has an almost unit
projection onto L . The Schumacher compressor simply transposes (via a permu-
tation mapping) the subspace L into the Hilbert space of a smaller block of nH VN
( r ) qubits. These proofs are not completely constructive.
Bennett [103] gave a constructive presentation of the Schumacher compression.
He observes that the Schumacher compression can be done by a unitary mapping to
a basis for which the density matrix r is diagonal (in certain simple cases the density
matrix r is already diagonal, e.g., when the input is a set of n identical qubits)
followed by certain combinatorial computation which we will call the Schumacher
compression function SCHUMACHER. The Schumacher compression function
SCHUMACHER simply orders the basis states first by the number of ones (from
smallest to largest) that are in the binary expansion of the bits and then refines this
order by a lexical sort of the the binary expansion of the bits. That is, all strings with
i ones are mapped before all strings with i+1 ones, and those strings with the same
number of ones are lexically ordered. Note that for any given value X of the qubits,
this transformation SCHUMACHER (X ) is simply a deterministic mapping from
an n bit sequence to a n 0 bit sequence defined by a combinatorial computation. In
particular, given an n bit binary string X, the transformation SCHUMACHER (X)
is the number of n bit strings so ordered before X.Itiseasytoshowthat
SCHUMACHER(X ) is a permutation. Since it is a permutation, it is a bijective
function which is uniquely reversible; it is also a unitary transformation. To insure
that the overall transformation (for all the states) is a quantum computation, it is
essential that the transformation SCHUMACHER (X)bedoneusingonly
reversible, quantum-coherent elementary operations. (Bennett et al. [104] gave a

o