Span Program for Non-binary Functions

Salman Beigi, Leila Taghavi

Span programs characterize the quantum query complexity of binary functions $f:\{0,\dots ,\ell {\}}^n\to \{0,1\}$ up to a constant factor. In this paper we generalize the notion of s…