2 papers
quant-ph2003
On Computational Power of Quantum Branching Programs
Farid Ablayev, Aida Gainutdinova, Marek Karpinski
In this paper we study a model of a Quantum Branching Program (QBP) and investigate its computational power. We prove a general lower bound on the width of read-once QBPs, which we…
quant-ph2002
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…