Title :
A quantum analog of Huffman coding
Author :
Braunstein, Samuel L. ; Fuchs, Christopher A. ; Gottesman, Daniel ; Lo, Hoi-Kwong
Author_Institution :
Wales Univ., Bangor, UK
Abstract :
We construct a Huffman-coding inspired scheme for quantum data compression. The number of computational steps in the encoding and decoding processes of N quantum signals can be made to be polynomial in log N by a massively parallel implementation of a quantum gate array. This is to be compared with the O(N3) computational steps required in the sequential implementation by Cleve and Di-Vincenzo (see Phys. Rev. A54, p.2636, 1996) of the Schumacher (see Phys. Rev. A51, p.2738, 1995) quantum noiseless block coding scheme
Keywords :
Huffman codes; computational complexity; decoding; quantum cryptography; source coding; Huffman coding; decoding; encoding; massively parallel implementation; polynomial; quantum analog; quantum data compression; quantum gate array; quantum noiseless block coding; quantum signals; sequential implementation; source coding; Block codes; Decoding; Eigenvalues and eigenfunctions; Encoding; Huffman coding; Length measurement; Magnetic heads; Performance evaluation; Quantum computing; Quantum mechanics;
Conference_Titel :
Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-7803-5000-6
DOI :
10.1109/ISIT.1998.708958
