{
  "annotation_id": "5e88918c-e956-43ee-9dd6-c2eca50f7a1e",
  "date_created": "2026-03-02T18:02:06.918000Z",
  "date_modified": "2026-03-02T18:02:06.918000Z",
  "file_hash": "296145401a78c7222e464d5f9f34bdab9181d2e01bb6f0c9c42715c36285d51b",
  "private": false,
  "record": {
    "abstract": "In this paper, the space complexity of nonuniform quantum computations is\ninvestigated. The model chosen for this are quantum branching programs, which\nprovide a graphic description of sequential quantum algorithms. In the first\npart of the paper, simulations between quantum branching programs and\nnonuniform quantum Turing machines are presented which allow to transfer lower\nand upper bound results between the two models. In the second part of the\npaper, different variants of quantum OBDDs are compared with their\ndeterministic and randomized counterparts. In the third part, quantum branching\nprograms are considered where the performed unitary operation may depend on the\nresult of a previous measurement. For this model a simulation of randomized\nOBDDs and exponential lower bounds are presented.",
    "arxiv_id": "quant-ph/0403164",
    "authors": [
      "M. Sauerhoff",
      "D. Sieling"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1016/j.tcs.2004.12.031",
    "journal_ref": "Theoretical Computer Science 334, pp. 177-225, 2005",
    "title": "Quantum Branching Programs and Space-Bounded Nonuniform Quantum   Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0403164"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "1756c8f7-ebc0-4c86-86ce-d889ac15016d",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}