Fidel Ernesto Diaz Andino

Unitary Branching Programs: Learnability and Lower Bounds

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…