Learning low-degree quantum objects
<|reference_start|>Learning low-degree quantum objects: 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.<|reference_end|>
@article{arunachalam2024learning,
    title={Learning low-degree quantum objects},
    author={Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Guti'errez,
  Carlos Palazuelos},
    journal={arXiv preprint arXiv:2405.10933},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.10933},
    primaryClass={quant-ph cs.CC cs.DS cs.LG math.FA}
}