dorsal/arxiv
View SchemaQuantum vs. Classical Read-once Branching Programs
| Authors | Martin Sauerhoff |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504198 |
| URL | https://arxiv.org/abs/quant-ph/0504198 |
Abstract
The paper presents the first nontrivial upper and lower bounds for (non-oblivious) quantum read-once branching programs. It is shown that the computational power of quantum and classical read-once branching programs is incomparable in the following sense: (i) A simple, explicit boolean function on 2n input bits is presented that is computable by error-free quantum read-once branching programs of size O(n^3), while each classical randomized read-once branching program and each quantum OBDD for this function with bounded two-sided error requires size 2^{\Omega(n)}. (ii) Quantum branching programs reading each input variable exactly once are shown to require size 2^{\Omega(n)} for computing the set-disjointness function DISJ_n from communication complexity theory with two-sided error bounded by a constant smaller than 1/2-2\sqrt{3}/7. This function is trivially computable even by deterministic OBDDs of linear size. The technically most involved part is the proof of the lower bound in (ii). For this, a new model of quantum multi-partition communication protocols is introduced and a suitable extension of the information cost technique of Jain, Radhakrishnan, and Sen (2003) to this model is presented.
{
"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
}