Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-013 | 3rd January 2004 00:00

Quantum and Stochastic Branching Programs of Bounded Width

RSS-Feed




Revision #1
Authors: Chris Pollett, Chris Ablayev, Chris Pollett, Farid Ablayev, Cristopher Moore
Accepted on: 3rd January 2004 00:00
Downloads: 3485
Keywords: 


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


Paper:

TR02-013 | 30th January 2002 00:00

Quantum and Stochastic Programs of Bounded Width


Abstract:

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.



ISSN 1433-8092 | Imprint