ECCC-Report TR02-013https://eccc.weizmann.ac.il/report/2002/013Comments and Revisions published for TR02-013en-usSat, 03 Jan 2004 00:00:00 +0200
Revision 1
| Quantum and Stochastic Branching Programs of Bounded Width |
Chris Pollett,
Chris Ablayev,
Chris Pollett,
Farid Ablayev,
Cristopher Moore
https://eccc.weizmann.ac.il/report/2002/013#revision1In 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.
Sat, 03 Jan 2004 00:00:00 +0200https://eccc.weizmann.ac.il/report/2002/013#revision1
Paper TR02-013
| Quantum and Stochastic Programs of Bounded Width |
Chris Pollett,
Farid Ablayev,
Cristopher Moore,
Chris Pollett
https://eccc.weizmann.ac.il/report/2002/013We 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.
Sat, 23 Feb 2002 18:54:00 +0200https://eccc.weizmann.ac.il/report/2002/013