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 main change over the original paper is the addition
of the syntactic restriction.

We prove upper and lower bounds on the power of quantum and stochastic
branching programs of bounded width. 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.