dorsal/arxiv
View SchemaThree Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State
| Authors | Paul Vitanyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9907035 |
| URL | https://arxiv.org/abs/quant-ph/9907035 |
| Journal | In: Proc. 15th IEEE Conf. Computational Complexity, 2000 |
Abstract
In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.
{
"annotation_id": "827f8690-c0d1-4b6c-aa43-1157591b7782",
"date_created": "2026-03-02T18:02:48.588000Z",
"date_modified": "2026-03-02T18:02:48.588000Z",
"file_hash": "8b10b6464ae1dc5991191d68a938f44b07118246bb276fb6f5fc8571bc58f185",
"private": false,
"record": {
"abstract": "In analogy of classical Kolmogorov complexity we develop a theory of the\nalgorithmic information in bits contained in any one of continuously many pure\nquantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity\ncoincides with the new quantum Kolmogorov complexity restricted to the\nclassical domain. Quantum Kolmogorov complexity is upper bounded and can be\neffectively approximated from above. With high probability a quantum object is\nincompressible. There are two alternative approaches possible: to define the\ncomplexity as the length of the shortest qubit program that effectively\ndescribes the object, and to use classical descriptions with computable real\nparameters.",
"arxiv_id": "quant-ph/9907035",
"authors": [
"Paul Vitanyi"
],
"categories": [
"quant-ph"
],
"journal_ref": "In: Proc. 15th IEEE Conf. Computational Complexity, 2000",
"title": "Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State",
"url": "https://arxiv.org/abs/quant-ph/9907035"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "97a40b9e-c0cd-4131-9032-17cae7b2bc6d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}