Carlos Palazuelos

We consider the problem of learning low-degree quantum objects up to ε-error in l_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.

Abstract We prove that two non-classical general probabilistic theories must give rise to entanglement, either at the level of states or at the level of measurements, when combined. This reveals a deep connection between a local phenomenon (non-classicality, or the existence of superpositions) and a global one (entanglement), and raises the latter to a generically non-classical rather than merely quantum phenomenon, in a precise mathematical sense. Instrumental in our proof is the solution of a long-standing conjecture by Barker.