However, the situation changes if the goal is to achieve a small worst-case prediction error rather than a small average prediction error — an exponential separation between \(N_{\mathrm {C}}\)  and \(N_{\mathrm {Q}}\)  becomes possible if we insist on predicting \(f(x)=\operatorname{tr}(O \operatorname{{\mathcal {E}}}(\vert x \rangle \! \langle x \vert ))\)  accurately for every input \(x\) .
We illustrate this point with an example: accurately predicting expectation values of Pauli observables in an unknown \(n\) -qubit quantum state \(\rho \) . This is a crucial subroutine in many quantum computing applications; see e.g. [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}.
We present a quantum ML model that uses \(N_{\mathrm {Q}}=\mathcal {O}(n)\)  copies of \(\rho \)  to predict expectation values of all \(n\) -qubit Pauli observables. In contrast we prove that any classical ML model requires \(N_{\mathrm {C}}=2^{\Omega (n)}\)  copies of \(\rho \)  to achieve the same task even if the classical ML can perform arbitrary adaptive single-copy POVM measurements.
