Quantum and Stochastic Branching Programs of Bounded Width
| dc.creator | Ablayev, Farid | |
| dc.creator | Moore, Cristopher | |
| dc.creator | Pollett, Chris | |
| dc.date | 2002-01-30 | |
| dc.date | 2004-01-03 | |
| dc.date.accessioned | 2026-07-07T06:03:36Z | |
| dc.date.available | 2026-07-07T06:03:36Z | |
| dc.description | 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. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0201139 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0201139 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90005 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum and Stochastic Branching Programs of Bounded Width | |
| dc.type | text |