Span program for non-binary functions

Span programs characterize the quantum query complexity of binary functions f:\{0,\ldots,\ell\}^n \to \{0,1\} up to a constant factor. In this paper we generalize the notion of span programs for functions with non-binary input/output alphabets f: [\ell]^n \to [m]. We show that non-binary span progra... View More