  We consider the problem of learning low-degree quantum objects up to
$\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$
unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and
unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of
$n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from
$d$-query quantum algorithms can be classically learned from
$O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which
implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$
polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through
$O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$.
Our main technical contributions are new Bohnenblust-Hille inequalities for
quantum channels and completely bounded~polynomials.
