{
  "annotation_id": "2a71cb3e-37e6-4538-bcb1-fd80577ce731",
  "date_created": "2026-03-02T18:02:27.038000Z",
  "date_modified": "2026-03-02T18:02:27.038000Z",
  "file_hash": "4010b085f49bdd92221973c383bdfa06a1c4495d2b94ef345990cebbd7e673bc",
  "private": false,
  "record": {
    "abstract": "We show that there exists a universal quantum Turing machine (UQTM) that can\nsimulate every other QTM until the other QTM has halted and then halt itself\nwith probability one. This extends work by Bernstein and Vazirani who have\nshown that there is a UQTM that can simulate every other QTM for an arbitrary,\nbut preassigned number of time steps. As a corollary to this result, we give a\nrigorous proof that quantum Kolmogorov complexity as defined by Berthiaume et\nal. is invariant, i.e. depends on the choice of the UQTM only up to an additive\nconstant. Our proof is based on a new mathematical framework for QTMs,\nincluding a thorough analysis of their halting behaviour. We introduce the\nnotion of mutually orthogonal halting spaces and show that the information\nencoded in an input qubit string can always be effectively decomposed into a\nclassical and a quantum part.",
    "arxiv_id": "quant-ph/0605030",
    "authors": [
      "Markus Mueller"
    ],
    "categories": [
      "quant-ph",
      "cs.IT",
      "math-ph",
      "math.IT",
      "math.MP"
    ],
    "doi": "10.1109/TIT.2007.913263",
    "journal_ref": "IEEE Trans. Inf. Th., Vol. 54/2 pp. 763-780 (2008)",
    "title": "Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov   Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0605030"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "3e73942a-e475-430f-ada0-990010a7a51b",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}