{
  "id": "oai:papers.qnfo.org:quantum-kolmogorov-complexity-a-family-of-uncomputable-description-length-measur",
  "slug": "quantum-kolmogorov-complexity-a-family-of-uncomputable-description-length-measur",
  "title": "Quantum Kolmogorov Complexity: A Family of Uncomputable Description-Length Measures",
  "authors": [
    "Rowan Brad Quni-Gudzinas"
  ],
  "abstract": "Quantum information processing lacks a universally accepted quantitative measure of the algorithmic content of quantum states: existing algorithmic information measures either describe quantum objects through classical strings or become infinite when applied directly to the continuum of quantum amplitudes. This gap blocks principled comparison of state-preparation costs and rigorous randomness certification. We define a family of quantum Kolmogorov complexity (QKC) measures as the length of the shortest quantum program that, executed on a universal deterministic-control quantum Turing machine, outputs a target state within a prescribed fidelity, with an additive fidelity penalty. We prove an invariance theorem showing that any two universal machines differ by at most an additive constant, and we establish uncomputability of exact QKC by reduction from classical Kolmogorov complexity. As a worked illustration, assuming a translator-program length of 120 bits and a classical Kolmogorov complexity of 500 bits for a 256-bit string, we derive the two-sided bound 380 ≤ K_U^ε(|x⟩) ≤ 620 bits, and with ε = 2^-10 a concrete 400-bit program yields the upper bound 410 bits. The framework gives quantum engineers and cryptographers a defined, if uncomputable, target quantity against which heuristic proxies such as circuit depth and entanglement entropy can be benchmarked.",
  "abstract_markdown": "Quantum information processing lacks a universally accepted quantitative measure of the algorithmic content of quantum states: existing algorithmic information measures either describe quantum objects through classical strings or become infinite when applied directly to the continuum of quantum amplitudes. This gap blocks principled comparison of state-preparation costs and rigorous randomness certification. We define a family of quantum Kolmogorov complexity (QKC) measures as the length of the shortest quantum program that, executed on a universal deterministic-control quantum Turing machine, outputs a target state within a prescribed fidelity, with an additive fidelity penalty. We prove an invariance theorem showing that any two universal machines differ by at most an additive constant, and we establish uncomputability of exact QKC by reduction from classical Kolmogorov complexity. As a worked illustration, assuming a translator-program length of 120 bits and a classical Kolmogorov complexity of 500 bits for a 256-bit string, we derive the two-sided bound $380 \\le K_U^{\\varepsilon}(|x\\rangle) \\le 620$ bits, and with $\\varepsilon = 2^{-10}$ a concrete 400-bit program yields the upper bound 410 bits. The framework gives quantum engineers and cryptographers a defined, if uncomputable, target quantity against which heuristic proxies such as circuit depth and entanglement entropy can be benchmarked.",
  "date": "2026-11-08",
  "first_published": "2026-11-08",
  "last_revised": "2026-11-08T00:00:00Z",
  "modified": "2026-11-08T00:00:00Z",
  "version": "1.0.0",
  "version_count": 1,
  "language": "en",
  "keywords": [],
  "quality_tags": [
    "High-quality scholarly research",
    "open-access scholarly work",
    "versioned research publication"
  ],
  "quality_label": "High-quality scholarly research",
  "quality_basis": "QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
  "quality_evidence_url": "https://qnfo.org/about",
  "peer_review_status": "Not independently peer-reviewed",
  "resource_type": "ScholarlyArticle",
  "doi": null,
  "doi_url": null,
  "url": "https://papers.qnfo.org/papers/quantum-kolmogorov-complexity-a-family-of-uncomputable-description-length-measur",
  "license_url": "https://legal.qnfo.org/",
  "license_spdx": null,
  "sha256": "53501d2f9d745d9b767467b0925a4cda575fed6405552f3e1a9fe48a327c602f",
  "version_url": "https://papers.qnfo.org/papers/quantum-kolmogorov-complexity-a-family-of-uncomputable-description-length-measur/v/1.0.0",
  "datacite": {
    "schemaVersion": "http://datacite.org/schema/kernel-4",
    "identifiers": [
      {
        "identifier": "https://papers.qnfo.org/papers/quantum-kolmogorov-complexity-a-family-of-uncomputable-description-length-measur",
        "identifierType": "URL"
      }
    ],
    "creators": [
      {
        "name": "Rowan Brad Quni-Gudzinas",
        "nameType": "Personal",
        "nameIdentifiers": [
          {
            "nameIdentifier": "https://orcid.org/0009-0002-4317-5604",
            "nameIdentifierScheme": "ORCID",
            "schemeUri": "https://orcid.org"
          }
        ]
      }
    ],
    "titles": [
      {
        "title": "Quantum Kolmogorov Complexity: A Family of Uncomputable Description-Length Measures"
      }
    ],
    "publisher": "QNFO",
    "publicationYear": "2026",
    "resourceType": {
      "resourceTypeGeneral": "Text",
      "resourceType": "ScholarlyArticle"
    },
    "subjects": [
      {
        "subject": "High-quality scholarly research",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "open-access scholarly work",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "versioned research publication",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      }
    ],
    "dates": [
      {
        "date": "2026-11-08",
        "dateType": "Issued"
      },
      {
        "date": "2026-11-08",
        "dateType": "Updated"
      }
    ],
    "language": "en",
    "version": "1.0.0",
    "rightsList": [
      {
        "rightsUri": "https://legal.qnfo.org/"
      }
    ],
    "descriptions": [
      {
        "description": "Quantum information processing lacks a universally accepted quantitative measure of the algorithmic content of quantum states: existing algorithmic information measures either describe quantum objects through classical strings or become infinite when applied directly to the continuum of quantum amplitudes. This gap blocks principled comparison of state-preparation costs and rigorous randomness certification. We define a family of quantum Kolmogorov complexity (QKC) measures as the length of the shortest quantum program that, executed on a universal deterministic-control quantum Turing machine, outputs a target state within a prescribed fidelity, with an additive fidelity penalty. We prove an invariance theorem showing that any two universal machines differ by at most an additive constant, and we establish uncomputability of exact QKC by reduction from classical Kolmogorov complexity. As a worked illustration, assuming a translator-program length of 120 bits and a classical Kolmogorov complexity of 500 bits for a 256-bit string, we derive the two-sided bound 380 ≤ K_U^ε(|x⟩) ≤ 620 bits, and with ε = 2^-10 a concrete 400-bit program yields the upper bound 410 bits. The framework gives quantum engineers and cryptographers a defined, if uncomputable, target quantity against which heuristic proxies such as circuit depth and entanglement entropy can be benchmarked.",
        "descriptionType": "Abstract"
      },
      {
        "description": "Publisher quality classification: High-quality scholarly research. QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
        "descriptionType": "Other"
      },
      {
        "description": "Peer review status: Not independently peer-reviewed",
        "descriptionType": "Other"
      }
    ],
    "formats": [
      "text/html"
    ]
  }
}