Abstract
We consider the problem of learning low-degree quantum objects up to ε-error in ℓ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/ε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/ε)d · 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/εd) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.