Learning low-degree quantum objects
This work addresses efficient learning of quantum systems for researchers in quantum computing and machine learning, offering new bounds and methods, though it appears incremental as it builds on existing inequalities and focuses on specific quantum objects.
The paper tackles the problem of learning low-degree quantum objects, such as channels, unitaries, and polynomials, up to ε-error in ℓ₂-distance, showing results like learning n-qubit degree-d quantum channels with O(1/ε^d) queries independent of n, and classically learning polynomials from quantum algorithms with O((1/ε)^d·log n) examples.
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 (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically 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\to [-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.