In the last section, we have derived a sample complexity lower bound for independent single-copy quantum measurements. Several results in the literature address this restricted setting, see e.g. [1]}, [2]}.
In stark contrast, very little is known about the more realistic setting of adaptive single-copy measurements; see [3]} for a (very recent) lower bound on quantum mixedness testing.
Here, we give an elementary proof that provides an exponential sample complexity lower bound for predicting Pauli expectation values based on single-copy adaptive measurements.
Such an extension to adaptive measurement strategies is nontrivial – very few results are known for this setting.
However, the actual result is not (yet) tight.
We believe that further improvements are possible using more sophisticated analysis and we leave this as a future work.
When adaptive measurements are allowed, each POVM measurement can depend on previous POVM measurement outcomes. And the entire training process can be written as
\(\rho \xrightarrow{} o_1, \rho \xrightarrow{} o_2, \,\, \ldots , \,\, \rho \xrightarrow{} o_N.\) 
