
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2005  Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V  
85267 22.04.2005 
On the Computational Power of Probabilistic and Quantum Branching Programs (Revised Version)
Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore and Christopher Pollett [Download PostScript] [Download PDF]
In this paper we show that onequbit polynomial time computations are as powerful as
NC^{1} circuits. More generally, we define syntactic models for quantum
and stochastic branching programs of bounded width and prove upper and lower bounds on
their power. We show that any NC^{1} language can be accepted exactly
by a width2 quantum branching program of polynomial length, in contrast to the
classical case where width 5 is necessary unless NC^{1} = ACC.
This separates width2 quantum programs from width2 doubly stochastic programs as we
show the latter cannot compute the middle bit of multiplication. Finally, we show that
boundedwidth quantum and stochastic programs can be simulated by classical programs
of larger but bounded width, and thus are in NC^{1}. 

Last Change:
04/22/05 at 10:18:22
English 
Universität Bonn > Institut für Informatik > Abteilung V 