On Computational Power of Quantum Branching Programs

Farid Ablayev , Aida Gainutdinova , Marek Karpinski

Authors on Pith no claims yet

classification 🪐 quant-ph

keywords branchingcomputationalpowerquantumalmostboundcertainfunction

read the original abstract

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 show to be almost tight on certain symmetric function.

This paper has not been read by Pith yet.

On Computational Power of Quantum Branching Programs

discussion (0)