We will first focus on non-adaptive measurements, where the POVM measurement for each copy is fixed and do not change throughout the training process, and show that any procedure needs to measure \(\Omega (n 2^n)\)  copies of the state \(\rho \) .
A matching upper bound can be obtained using classical shadows with random Clifford measurements [1]}. Classical shadows with random Clifford measurements can predict \(M\)  observables \(O_1, \ldots , O_M\)  using only \(N_{\mathrm {C}} = \mathcal {O}(\max _{i} \operatorname{tr}(O_i^2)\log (M))\)  copies.
For the set of all \(n\) -qubit Pauli observables, we have \(\operatorname{tr}(P_i^2) = 2^n\)  and \(M = 4^n\) , so \(N_{\mathrm {C}} = \mathcal {O}(n 2^n)\) .
This matches with the lower bound for non-adaptive measurements.
