On Computational Power of Quantum Branching Programs

In this paper we introduce a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2n), contrary to the analogous situation for quantum finite automata. Further we display certain symmetric Boolean function which is computable by a read-once QBP with O(logn) width, which requires a width Ω(n) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions in each levels.We present a general lower bound for the width of read-once QBPs, showing that the upper bound for the considered symmetric function is almost tight.