Learning low-degree quantum objects

Abstract

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 (which is independent of $n$), $(ii)$ polynomials $p:{-1,1}^n→ [-1,1]$ arising from $d$-query quantum algorithms can be 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 → [-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.