dorsal/arxiv
View SchemaQuantum and Stochastic Branching Programs of Bounded Width
| Authors | Farid Ablayev, Cristopher Moore, Chris Pollett |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0201139 |
| URL | https://arxiv.org/abs/quant-ph/0201139 |
Abstract
In this paper we show that one qubit polynomial time computations are at least as powerful as $\NC^1$ circuits. More precisely, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show any $\NC^1$ language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless $\NC^1=\ACC$. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in $\NC^1$. The change in the revised version is the addition of the syntactic condition.
{
"annotation_id": "23805bbc-151f-48c9-9b6d-123bba750c04",
"date_created": "2026-03-02T18:01:48.836000Z",
"date_modified": "2026-03-02T18:01:48.836000Z",
"file_hash": "5c46d352eeb5ea3f3c196f92669666100dce090cd38352b685f92cd8b6c59da0",
"private": false,
"record": {
"abstract": "In this paper we show that one qubit polynomial time computations are at\nleast as powerful as $\\NC^1$ circuits. More precisely, we define syntactic\nmodels for quantum and stochastic branching programs of bounded width and prove\nupper and lower bounds on their power. We show any $\\NC^1$ language can be\naccepted exactly by a width-2 quantum branching program of polynomial length,\nin contrast to the classical case where width 5 is necessary unless\n$\\NC^1=\\ACC$. This separates width-2 quantum programs from width-2 doubly\nstochastic programs as we show the latter cannot compute the middle bit of\nmultiplication. Finally, we show that bounded-width quantum and stochastic\nprograms can be simulated by classical programs of larger but bounded width,\nand thus are in $\\NC^1$. The change in the revised version is the addition of\nthe syntactic condition.",
"arxiv_id": "quant-ph/0201139",
"authors": [
"Farid Ablayev",
"Cristopher Moore",
"Chris Pollett"
],
"categories": [
"quant-ph"
],
"title": "Quantum and Stochastic Branching Programs of Bounded Width",
"url": "https://arxiv.org/abs/quant-ph/0201139"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cd8db5f2-5af2-47dd-ab00-0e9181280bf6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}