Unitary Branching Programs: Learnability and Lower Bounds

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

[ Abstract ] [ Livestream: Visit Semisupervised and Unsupervised Learning 2 ] [ Paper ]
Thu 22 Jul 5:20 p.m. — 5:25 p.m. PDT

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.