Learning low-degree quantum objects

We consider the problem of learning low-degree quantum objects up to ε-error in ₂-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/εᵈ) queries (independent of n), $(ii)$ polynomials p:\-1,1\ⁿ→ [-1,1] arising from d-query quantum algorithms can be classically learned from O((1/ε)ᵈ· 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\ⁿ→ [-1,1] can be learned through O(1/εᵈ) queries to a quantum unitary Uₚ that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.