Skip to yearly menu bar Skip to main content


Unitary Branching Programs: Learnability and Lower Bounds

Fidel Ernesto Diaz Andino · Maria Kokkou · Mateus de Oliveira Oliveira · Farhad Vadiee


Keywords: [ Large Deviations a ] [ Algorithms -> Boosting and Ensemble Methods; Algorithms -> Model Selection and Structure Learning; Theory ] [ Regression ] [ Algorithms ] [ Active Learning ]


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 of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.

Chat is not available.