About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.