Improved regret bounds for structured online learning of quantum states

Quantum state tomography is essential for verifying and analyzing quantum systems but is notoriously resource-intensive. Recent advances such as shadow tomography reduce the sample complexity by focusing on estimating specific properties rather than the full state. However, existing methods assume static measurement settings and binary outcomes, limiting their applicability in dynamic or adversarial environments. To address the limitations of shadow tomography in dynamic or adversarial settings, Aaronson et al. (NeurIPS'18) introduced the framework of online learning for quantum states, where measurements arrive sequentially and the learner must make predictions in real time. This work explores the online learning framework for quantum states, where measurements arrive sequentially and possibly adversarially. In this work, we analyze a slight variant of the Projected Online Gradient Descent -- that achieves improved regret bounds in scenarios with structured or low-rank measurements. We further demonstrate that when the loss is measured via squared l_2-distance over k-outcome measurements, a simple analysis on an existing algorithm yields logarithmic regret.