Predicting adaptively chosen observables in quantum systems
This addresses a critical issue for quantum experimentalists by revealing how adaptivity can increase sample complexity and providing algorithms to prevent errors in predictions.
The paper tackles the problem of predicting observables in quantum systems when the choice of observables adapts based on previous data, showing that for local and Pauli observables, at least Ω(√M) samples are necessary, while for bounded-Frobenius-norm observables, only O(log M) samples suffice.
Recent advances have demonstrated that $\mathcal{O}(\log M)$ measurements suffice to predict $M$ properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that $Ω(\sqrt{M})$ samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of $M$ adaptively chosen local and Pauli observables. We also present computationally-efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only $\mathcal{O}(\log M)$ samples, independent of system size. Our results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide new algorithmic tools to safeguard against erroneous predictions in quantum experiments.