A Quantum Analog of Huffman Coding

Braunstein, Samuel L. ; Fuchs, Christopher A. ; Gottesman, Daniel ; Lo, Hoi-Kwong

HP Development Company

关键词: Huffman coding;    variable length codes;    instantaneous codes;    quantum information;    quantum computing;   

RP-ID  :  HPL-98-23

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We analyse a generalization of Huffman coding to the quantum case. In particular, we notice various difficulties in using instantaneous codes for quantum communication. However, for the storage of quantum information, we have succeeded in constructing a Huffman-coding inspired quantum scheme. 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 DiVincenzo to the well-known quantum noiseless block coding scheme by Schumacher. The powers and limitations in using this scheme in communications are also discussed. 11 Pages