Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 1, 2000 | public
Journal Article Open

A quantum analog of Huffman coding

Abstract

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.

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.

Files

BRAieeetit00.pdf
Files (165.4 kB)
Name Size Download all
md5:94e483c8301fc4fef28a457da0d40ed9
165.4 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 16, 2023