A Caltech Library Service

A quantum analog of Huffman coding

Braunstein, Samuel L. and Fuchs, Christopher A. and Gottesman, Daniel and Lo, Hoi-Kwong (2000) A quantum analog of Huffman coding. IEEE Transactions on Information Theory, 46 (4). pp. 1644-1649. ISSN 0018-9448.

See Usage Policy.


Use this Persistent URL to link to this item:


We analyze a generalization of Huffman coding to the quantum case. In particular, we notice various difficulties in using instantaneous codes for quantum communication. Nevertheless, 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 of polylogarithmic depth 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 (see Phys. Rev., vol.A54, p.2636, 1996) of the well-known quantum noiseless block-coding scheme of Schumacher. We also show that O(N2(log N)a) sequential computational steps are needed for the communication of quantum information using another Huffman coding inspired scheme where the sender must disentangle her encoding device before the receiver can perform any measurements on his signals.

Item Type:Article
Additional Information:© Copyright 2000 IEEE. Reprinted with permission. Manuscript received May 7, 1999; revised January 11, 2000. This work was supported in part by EPSRC under Grants GR/L91344 and GR/L80676, by the Lee A. DuBridge Fellowship, by DARPA under Grant DAAH04-96-1-0386 through the Quantum Information and Computing (QUIC) Institute administered by ARO, and by the U.S. Department of Energy under Grant DE-FG03-92-ER40701. The work of H.-K. Lo was performed while the author was with Hewlett-Packard Laboratories, Bristol, U.K. Communicated by A. M. Barg, Associate Editor for Coding Theory. H.-K. Lo would like to thank D. P. DiVincenzo, J. Preskill, and T. Spiller for helpful discussions.
Subject Keywords:Huffman codes; computational complexity; decoding; logic arrays; optical logic; parallel processing; quantum cryptography; source coding
Record Number:CaltechAUTHORS:BRAieeetit00
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4581
Deposited By: Archive Administrator
Deposited On:29 Aug 2006
Last Modified:26 Dec 2012 09:00

Repository Staff Only: item control page