dorsal/arxiv
View SchemaCompression of sources of probability distributions and density operators
| Authors | Andreas Winter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0208131 |
| URL | https://arxiv.org/abs/quant-ph/0208131 |
Abstract
We study the problem of efficient compression of a stochastic source of probability distributions. It can be viewed as a generalization of Shannon's source coding problem. It has relation to the theory of common randomness, as well as to channel coding and rate--distortion theory: in the first two subjects ``inverses'' to established coding theorems can be derived, yielding a new approach to proving converse theorems, in the third we find a new proof of Shannon's rate--distortion theorem. After reviewing the known lower bound for the optimal compression rate, we present a number of approaches to achieve it by code constructions. Our main results are: a better understanding of the known lower bounds on the compression rate by means of a strong version of this statement, a review of a construction achieving the lower bound by using common randomness which we complement by showing the optimal use of the latter within a class of protocols. Then we review another approach, not dependent on common randomness, to minimizing the compression rate, providing some insight into its combinatorial structure, and suggesting an algorithm to optimize it. The second part of the paper is concerned with the generalization of the problem to quantum information theory: the compression of mixed quantum states. Here, after reviewing the known lower bound we contribute a strong version of it, and discuss the relation of the problem to other issues in quantum information theory.
{
"annotation_id": "f96fd6ed-6d65-47a6-b19b-bb4d88092421",
"date_created": "2026-03-02T18:01:53.103000Z",
"date_modified": "2026-03-02T18:01:53.103000Z",
"file_hash": "c1e142c35e9cb6c704d49af2974f72969031145ba085e21001f64d9eb9dc4a70",
"private": false,
"record": {
"abstract": "We study the problem of efficient compression of a stochastic source of\nprobability distributions. It can be viewed as a generalization of Shannon\u0027s\nsource coding problem. It has relation to the theory of common randomness, as\nwell as to channel coding and rate--distortion theory: in the first two\nsubjects ``inverses\u0027\u0027 to established coding theorems can be derived, yielding a\nnew approach to proving converse theorems, in the third we find a new proof of\nShannon\u0027s rate--distortion theorem.\n After reviewing the known lower bound for the optimal compression rate, we\npresent a number of approaches to achieve it by code constructions. Our main\nresults are: a better understanding of the known lower bounds on the\ncompression rate by means of a strong version of this statement, a review of a\nconstruction achieving the lower bound by using common randomness which we\ncomplement by showing the optimal use of the latter within a class of\nprotocols. Then we review another approach, not dependent on common randomness,\nto minimizing the compression rate, providing some insight into its\ncombinatorial structure, and suggesting an algorithm to optimize it.\n The second part of the paper is concerned with the generalization of the\nproblem to quantum information theory: the compression of mixed quantum states.\nHere, after reviewing the known lower bound we contribute a strong version of\nit, and discuss the relation of the problem to other issues in quantum\ninformation theory.",
"arxiv_id": "quant-ph/0208131",
"authors": [
"Andreas Winter"
],
"categories": [
"quant-ph"
],
"title": "Compression of sources of probability distributions and density operators",
"url": "https://arxiv.org/abs/quant-ph/0208131"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "59671451-2c7d-44f6-9d20-6b5d1d9195e5",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}