# Online Learning of Quantum States

arXiv: https://arxiv.org/abs/1802.09025 · HTML: https://mlsanity.com/paper/1802.09025/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2018.

## Built on by (most cited first, 30 of 37)

- [On quantum backpropagation, information reuse, and cheating measurement collapse](https://mlsanity.com/paper/2305.13362/) (2023)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Flexible learning of quantum states with generative query neural networks](https://mlsanity.com/paper/2202.06804/) (2022)
- [Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States](https://mlsanity.com/paper/2202.02765/) (2022)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [ShadowNet for Data-Centric Quantum System Learning](https://mlsanity.com/paper/2308.11290/) (2023)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States](https://mlsanity.com/paper/2210.00997/) (2022)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Online learning of a panoply of quantum objects](https://mlsanity.com/paper/2406.04245/) (2024)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Learning in quantum games](https://mlsanity.com/paper/2302.02333/) (2023)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Exponential Quantum Communication Advantage in Distributed Inference and Learning](https://mlsanity.com/paper/2310.07136/) (2023)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (2023)
- [Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography](https://mlsanity.com/paper/2211.12880/) (2022)
- [Online Convex Optimization of Programmable Quantum Computers to Simulate Time-Varying Quantum Channels](https://mlsanity.com/paper/2212.05145/) (2022)
- [Online Learning Quantum States with the Logarithmic Loss via VB-FTRL](https://mlsanity.com/paper/2311.04237/) (2023)
- [Online Learning of Pure States is as Hard as Mixed States](https://mlsanity.com/paper/2502.00823/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes](https://mlsanity.com/paper/2308.12304/) (2023)

## Abstract (arXiv)

Suppose we have many copies of an unknown n-qubit state ρ. We measure some copies of ρ using a known two-outcome measurement E1, then other copies using a measurement E2, and so on. At each stage t, we generate a current hypothesis σt about the state ρ, using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that |operatornameTr(Ei σt) - operatornameTr(Eiρ) |, the error in our prediction for the next measurement, is at least varepsilon at most operatornameO!left(n / varepsilon2 right)  times. Even in the "non-realizable" setting---where there could be arbitrary noise in the measurement outcomes---we show how to output hypothesis states that do significantly worse than the best possible states at most operatornameO!left(√ Tnright)  times on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results---using convex optimization, quantum postselection, and sequential fat-shattering dimension---which have different advantages in terms of parameters and portability.