dorsal/arxiv
View SchemaQuantum Kolmogorov complexity and its applications
| Authors | C. Mora, H. Briegel, B. Kraus |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610109 |
| URL | https://arxiv.org/abs/quant-ph/0610109 |
Abstract
Kolmogorov complexity is a measure of the information contained in a binary string. We investigate here the notion of quantum Kolmogorov complexity, a measure of the information required to describe a quantum state. We show that for any definition of quantum Kolmogorov complexity measuring the number of classical bits required to describe a pure quantum state, there exists a pure n-qubit state which requires exponentially many bits of description. This is shown by relating the classical communication complexity to the quantum Kolmogorov complexity. Furthermore we give some examples of how quantum Kolmogorov complexity can be applied to prove results in different fields, such as quantum computation and thermodynamics, and we generalize it to the case of mixed quantum states.
{
"annotation_id": "130233a3-c082-4539-a293-84a9dcf573fd",
"date_created": "2026-03-02T18:02:31.250000Z",
"date_modified": "2026-03-02T18:02:31.250000Z",
"file_hash": "15b1facd4eef9ed033df3b8b033706be3d40630654149124641d99f64b475853",
"private": false,
"record": {
"abstract": "Kolmogorov complexity is a measure of the information contained in a binary\nstring. We investigate here the notion of quantum Kolmogorov complexity, a\nmeasure of the information required to describe a quantum state. We show that\nfor any definition of quantum Kolmogorov complexity measuring the number of\nclassical bits required to describe a pure quantum state, there exists a pure\nn-qubit state which requires exponentially many bits of description. This is\nshown by relating the classical communication complexity to the quantum\nKolmogorov complexity. Furthermore we give some examples of how quantum\nKolmogorov complexity can be applied to prove results in different fields, such\nas quantum computation and thermodynamics, and we generalize it to the case of\nmixed quantum states.",
"arxiv_id": "quant-ph/0610109",
"authors": [
"C. Mora",
"H. Briegel",
"B. Kraus"
],
"categories": [
"quant-ph"
],
"title": "Quantum Kolmogorov complexity and its applications",
"url": "https://arxiv.org/abs/quant-ph/0610109"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1d039fbf-e080-4865-b33a-c4003d06db99",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}