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

polynomial time quantum algorithm for the related problem of extraction of only
classical information from a quantum noiseless coding.) Cleve, DiVincenzo [105]
then developed the first polynomial time algorithm for Schumacher noiseless
compression of n qubits. In particular, they explicitly computed the bijective
function SCHUMACHER (X) and it's reverse using O(n 3 ) reversible, elementary
unitary operations. This was previously the fastest previous algorithm for the
Schumacher encoding and decoding functions. Recently, Reif and Chakraborty
[108] gave a time efficient algorithm for asymptotically optimal noiseless quantum
compression and decompression, costing only O ð n ð log 4 n Þ log log n Þ elementary
quantum operations. This modified Schumacher encoding requires the evaluation
of various combinatorial sums, for which Reif and Chakraborty provide efficient
recursive, reversible quantum algorithms. The coding of [106] employed a modified
Schumacher encoding that was still asymptotically optimal in fidelity and size.
The Schumacher quantum noiseless coding theorem assumes the compressor
knows the source. Jozsa et al. [107] recently gave a generalization of the Schumacher
compression, that is, the compressor does not know the source, and thus provides
the first asymptotically optimal universal algorithm for quantum compression.
Also, Braustein et al. [108] have recently given a fast algorithm for an quantum
analog of Huffman coding, but do not provide a proof that this coding gives
asymptotically optimal noiseless quantum compression (that is, reaches the von
Neumann entropy), as provided by Schumacher compression. ([102] assumes the
compressor knows the source, but can be extended using the techniques of Jozsa
et al. [107] to a asymptotically optimal universal algorithm for quantum compres-
sion where the compressor does not know the source.)
3.6. QUANTUM ERROR-CORRECTING CODES
3.6.1. Quantum Coding Theory
The qubit can be defined in quantum information theory as the amount of
information that can be carried in a quantum system with two basis states, e.g., the
internal degree of freedom of a polarized photon. The qubit is thus a fundamental
unit of quantum channel capacity. Nielsen [109] (Svozil [110, 111], Holevo [112],
Knill, Laflamme [113, 114], and Ohya [115] develop a theory of quantum error-
correcting codes and quantum information theory, e.g., they give the definition of
quantum mutual entropy for an entangled state. Buhrman et al. [116], and
Adami, Cerf [117] contrast quantum information theory with classical informa-
tion theory. Quantum channel capacity has been investigated for noisy channels
(DiVincenzo, et al. [118], Holevo [119], Barnum et al. [120]), very noisy channels
(Shor, Smolin [121]), and quantum erasure channels (Bennett et al. [122]). Fuchs
[123] showed that nonorthogonal quantum states maximize classical information
capacity. (Also, Helstrom [124, 125] defines a quantum theory of infor-
mation detection, and Fuchs [126] defines a related quantum theory of informa-
tion distinguishability.)