{
  "annotation_id": "5c6a9415-c9bc-481b-a933-210adecaa904",
  "date_created": "2026-03-02T18:01:38.732000Z",
  "date_modified": "2026-03-02T18:01:38.732000Z",
  "file_hash": "3aca6e19774deefb15e55d72969e10bf158ae0ae1d3c7c672def1e2482a5e2b0",
  "private": false,
  "record": {
    "abstract": "In this paper we give a definition for quantum Kolmogorov complexity. In the\nclassical setting, the Kolmogorov complexity of a string is the length of the\nshortest program that can produce this string as its output. It is a measure of\nthe amount of innate randomness (or information) contained in the string.\n  We define the quantum Kolmogorov complexity of a qubit string as the length\nof the shortest quantum input to a universal quantum Turing machine that\nproduces the initial qubit string with high fidelity. The definition of Vitanyi\n(Proceedings of the 15th IEEE Annual Conference on Computational Complexity,\n2000) measures the amount of classical information, whereas we consider the\namount of quantum information in a qubit string. We argue that our definition\nis natural and is an accurate representation of the amount of quantum\ninformation contained in a quantum state.",
    "arxiv_id": "quant-ph/0005018",
    "authors": [
      "Andre Berthiaume",
      "Wim van Dam",
      "Sophie Laplante"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1006/jcss.2001.1765",
    "journal_ref": "Journal of Computer and Systems Sciences, Volume 63, No. 2,\n  September 2001, pages 201-221",
    "title": "Quantum Kolmogorov Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0005018"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e889d729-181d-41ef-adc6-969d96ccea97",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}