  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.
