dorsal/arxiv
View SchemaSchumacher's quantum data compression as a quantum computation
| Authors | Richard Cleve, David P. DiVincenzo |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9603009 |
| URL | https://arxiv.org/abs/quant-ph/9603009 |
| DOI | 10.1103/PhysRevA.54.2636 |
Abstract
An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary strings. The algorithm, which adheres to the rules of reversible programming, is expressed in a high-level pseudocode language. It is implemented using $O(n^3)$ two- and three-bit primitive reversible operations, where $n$ is the length of the qubit strings to be compressed. Also, the algorithm makes use of $O(n)$ auxiliary qubits; however, space-saving techniques based on those proposed by Bennett are developed which reduce this workspace to $O(\sqrt{n})$ while increasing the running time by less than a factor of two.
{
"annotation_id": "cf7c4ea6-9457-49ac-8063-e2ae58ac2a78",
"date_created": "2026-03-02T18:02:37.380000Z",
"date_modified": "2026-03-02T18:02:37.380000Z",
"file_hash": "f952dcac7a62c2b746c00b409758394b40fc7763fcb46c01e42e9d7a39cd416e",
"private": false,
"record": {
"abstract": "An explicit algorithm for performing Schumacher\u0027s noiseless compression of\nquantum bits is given. This algorithm is based on a combinatorial expression\nfor a particular bijection among binary strings. The algorithm, which adheres\nto the rules of reversible programming, is expressed in a high-level pseudocode\nlanguage. It is implemented using $O(n^3)$ two- and three-bit primitive\nreversible operations, where $n$ is the length of the qubit strings to be\ncompressed. Also, the algorithm makes use of $O(n)$ auxiliary qubits; however,\nspace-saving techniques based on those proposed by Bennett are developed which\nreduce this workspace to $O(\\sqrt{n})$ while increasing the running time by\nless than a factor of two.",
"arxiv_id": "quant-ph/9603009",
"authors": [
"Richard Cleve",
"David P. DiVincenzo"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.54.2636",
"title": "Schumacher\u0027s quantum data compression as a quantum computation",
"url": "https://arxiv.org/abs/quant-ph/9603009"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0a78b38d-8bbe-4c85-8372-4eaddd010b2f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}