Richard Kueng

Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample- efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime k we construct explicit learning tasks of degree k, which are exponentially hard with (k − 1)-copy measurements but efficiently solvable with k- copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks ex- ist for all square-free integers k, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning prob- lems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage

Abstract Machine learning (ML) provides the potential to solve challenging quantum many-body problems in physics and chemistry. Yet, this prospect has not been fully justified. In this work, we establish rigorous results to understand the power of classical ML and the potential for quantum advantage in an important example application: predicting outcomes of quantum mechanical processes. We prove that for achieving a small average prediction error, one can always design a classical ML model whose sample complexity is comparable to the best quantum ML model (up to a small polynomial factor). Regarding computational complexity, we show that the class of problems that can be solved by efficient classical ML models with access to sampled data is strictly larger than BPP. Hence, classical ML models may be able to solve some challenging quantum problems after training from data obtained in physical experiments. As a concrete example, we prove that a simple, classical ML model can efficiently learn to predict ground state representations that approximate expectation values of local observables up to a small, constant error. This holds for any smooth family of gapped local Hamiltonians in a finite spatial dimension.