{
  "annotation_id": "7f4c6223-92d2-4871-8ec7-6b2cddf3f904",
  "date_created": "2026-03-02T18:02:17.205000Z",
  "date_modified": "2026-03-02T18:02:17.205000Z",
  "file_hash": "f964ef7e23807f2054ea52fd27a43db12e764e20a7ed25069fc78a4ec087c549",
  "private": false,
  "record": {
    "abstract": "The paper presents the first nontrivial upper and lower bounds for\n(non-oblivious) quantum read-once branching programs. It is shown that the\ncomputational power of quantum and classical read-once branching programs is\nincomparable in the following sense: (i) A simple, explicit boolean function on\n2n input bits is presented that is computable by error-free quantum read-once\nbranching programs of size O(n^3), while each classical randomized read-once\nbranching program and each quantum OBDD for this function with bounded\ntwo-sided error requires size 2^{\\Omega(n)}. (ii) Quantum branching programs\nreading each input variable exactly once are shown to require size\n2^{\\Omega(n)} for computing the set-disjointness function DISJ_n from\ncommunication complexity theory with two-sided error bounded by a constant\nsmaller than 1/2-2\\sqrt{3}/7. This function is trivially computable even by\ndeterministic OBDDs of linear size. The technically most involved part is the\nproof of the lower bound in (ii). For this, a new model of quantum\nmulti-partition communication protocols is introduced and a suitable extension\nof the information cost technique of Jain, Radhakrishnan, and Sen (2003) to\nthis model is presented.",
    "arxiv_id": "quant-ph/0504198",
    "authors": [
      "Martin Sauerhoff"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum vs. Classical Read-once Branching Programs",
    "url": "https://arxiv.org/abs/quant-ph/0504198"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "01c7a8cf-fc3e-4b30-be50-d941e46cc8a5",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}