Finite-Size Limits of Adaptive Pauli Prediction

Can quantum data reliably answer questions chosen from earlier results? We prove that M adaptive Pauli predictions on n qubits require Ω(sqrt n,M) copies at fixed accuracy. Published upper bounds make this tight for M n. Thus n adaptive predictions cost Θ(sqrt n) copies, whereas a fixed list costs only O(n). The lower bound uses diagonal states and commuting observables, identifying a statistical cost of adaptation. We also quantify how this cost increases with precision.