A quantum analog of Huffman coding

DOI10.1109/18.850709MaRDI QIDQ4503601zbMATH OpenOpenAlexFDO

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

Publication date 7 September 2000

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9805080, https://resolver.caltech.edu/CaltechAUTHORS:BRAieeetit00

zbMATH Keywords

data compressionHuffman codinginstantaneous codesquantum communicationquantum informationvariable-length codes

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Quantum computation (81P68) Prefix, length-variable, comma-free codes (94A45)

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 (N^3) computational steps required in the sequential implementation by Cleve and DiVincenzo of the well-known quantum noiseless block coding scheme of Schumacher. We also show that O(N^2(log N)^a) 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.

Recommendations

• Lower bound on expected communication cost of quantum Huffman coding
• Reversible arithmetic coding for quantum data compression
• Dense quantum coding and quantum finite automata
• On Lossless Quantum Data Compression With a Classical Helper
• Simple construction of quantum universal variable-length source coding

Cited in

(8)

• Efficient and exact quantum compression
• Lossless quantum data compression and quantum Kolmogorov complexity
• Dense quantum coding and quantum finite automata
• Reversible arithmetic coding for quantum data compression
• Asymptotic redundancies for universal quantum coding
• A dynamical systems proof of Kraft-McMillan inequality and its converse for prefix-free codes
• Lower bound on expected communication cost of quantum Huffman coding
• A theoretical framework for quantum image representation and data loading scheme

This page was built for publication: A quantum analog of Huffman coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4503601)