Quantum and Stochastic Branching Programs of Bounded Width

Farid Ablayev, Cristopher Moore, Chris Pollett

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 stochasti…