Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination Neeiporuk's lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.
We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-
k-times Branching Programs or Ordered Binary Decision Diagrams with repeated test (
k-QOBDD,
k-NOBDD and
k-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of
k-OBDD.