dorsal/arxiv
View SchemaA quantum analog of Huffman coding
| Authors | Samuel L. Braunstein, Christopher A. Fuchs, Daniel Gottesman, Hoi-Kwong Lo |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9805080 |
| URL | https://arxiv.org/abs/quant-ph/9805080 |
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.
{
"annotation_id": "500bd0bc-a954-4b98-afe8-f9758f41713b",
"date_created": "2026-03-02T18:02:45.249000Z",
"date_modified": "2026-03-02T18:02:45.249000Z",
"file_hash": "f8fdd3073765fa8738f588403ed23b9018580d83d796bd96ea22928543f45a03",
"private": false,
"record": {
"abstract": "We analyze a generalization of Huffman coding to the quantum case. In\nparticular, we notice various difficulties in using instantaneous codes for\nquantum communication. Nevertheless, for the storage of quantum information, we\nhave succeeded in constructing a Huffman-coding inspired quantum scheme. The\nnumber of computational steps in the encoding and decoding processes of N\nquantum signals can be made to be of polylogarithmic depth by a massively\nparallel implementation of a quantum gate array. This is to be compared with\nthe O (N^3) computational steps required in the sequential implementation by\nCleve and DiVincenzo of the well-known quantum noiseless block coding scheme of\nSchumacher. We also show that O(N^2(log N)^a) computational steps are needed\nfor the communication of quantum information using another Huffman-coding\ninspired scheme where the sender must disentangle her encoding device before\nthe receiver can perform any measurements on his signals.",
"arxiv_id": "quant-ph/9805080",
"authors": [
"Samuel L. Braunstein",
"Christopher A. Fuchs",
"Daniel Gottesman",
"Hoi-Kwong Lo"
],
"categories": [
"quant-ph"
],
"title": "A quantum analog of Huffman coding",
"url": "https://arxiv.org/abs/quant-ph/9805080"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b91395e4-ab83-4705-a3e5-37a1c6dcdbe1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}