Research map / Bandits and online learning / Online convex optimization and games
Online Learning of Pure States is as Hard as Mixed States
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that online learning of pure n-qubit states has the same sequential fat-shattering dimension (and hence regret scaling Θ(√(nT)) under L1 loss) as mixed states, and extends results to ε-realizable and smoothed settings.
Problem
Whether pure-state tomography, which is substantially easier than mixed-state tomography offline, is also easier in the adversarial online learning setting; the regret scaling of online quantum state learning for pure vs mixed states.
Approach
Builds explicit X-valued and real-valued binary trees (Von Neumann, halving, and Von Neumann halving trees) and realizes each path as a pure state (or a completion of a partial matrix) to lower bound the sequential fat-shattering dimension of pure states by Ω(n/δ^η) for η<2, matching mixed states up to the range of η, thereby giving identical regret scaling.
Key results
- Pure-state sequential fat-shattering dimension is Ω(n/δ^η) for all η<2, matching the mixed-state bound up to the range of η, so the L1 minimax regret for pure states is Ω(√(nT)).
- Under the epsilon-realizable setting, the minimax regret is Θ(√(nT)) independent of ε.
- Under σ-smoothed adversaries, the regret for pure states is O(√(nT log T / σ)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the hypothesis class from all quantum states to pure states | Online quantum state learning with general measurements · General measurements, n-qubit states | sequential fat-shattering dimension: \Theta(\frac{n}{\delta^2}) vs. \Omega(\frac n{\delta^\eta}), \forall\eta < 2 | No clear effect |
| Restrict the hypothesis class from all quantum states to pure states | Online quantum state learning with general measurements · General measurements, n-qubit states, L1 loss | minimax regret: \Theta(\sqrt{nT}) | No clear effect |
| Restrict the hypothesis class from all quantum states to pure states | Online quantum state learning with general measurements · General measurements, n-qubit states, L2 loss | minimax regret: \Omega(\sqrt{nT}) | No clear effect |
| Use epsilon-realizable feedback instead of fully adversarial labels | Online quantum state learning · General measurements, epsilon-realizable setting | minimax regret: \Theta(\sqrt{nT}) | No clear effect |
| Restrict adversarial measurement distributions to be sigma-smooth around a target distribution | Online learning of n-qubit pure states · General measurements, smoothed setting | minimax regret: O\Bigg(\sqrt{\frac{nT \log T}{\sigma}} \ \Bigg) | Mixed |
Surprising findings
- Restricting states to rank 1 does not reduce the sequential fat-shattering lower bound, unlike rank-dependent behavior in classical settings.
- Pure and mixed states have identical online regret scaling, even though offline sample complexity differs (N vs N^3).
Limitations
- Lower bound for pure states on the standard fat-shattering dimension is Ω(1/δ²) rather than Ω(n/δ²); the offline n-dependence is open.
- Lower bound for L2 loss may be loose and holds only for T ≤ 4^n.
- Smoothed upper bound's tightness is open.
Experimental setup
Metrics: sequential fat-shattering dimension minimax regret
Baselines: mixed-state online quantum state learning bounds
Builds on: sequential fat-shattering dimension (Rakhlin et al.) online quantum state learning regret bounds (Aaronson-type / Shaw et al.) smoothed online learning (Haghtalab et al.) positive semidefinite matrix completion (chordal graphs)
Closest papers by meaning
- Purest Quantum State Identification (NeurIPS 2025 · similarity 0.88)
- On the Trainability and Classical Simulability of Learning Matrix Product States Variationally (AAAI 2025 · similarity 0.86)
- Reinforced Learning Explicit Circuit Representations for Quantum State Characterization from Local Measurements (ICML 2025 · similarity 0.85)
- Limitations of measure-first protocols in quantum machine learning (ICML 2025 · similarity 0.85)
- SSL4Q: Semi-Supervised Learning of Quantum Data with Application to Quantum State Classification (ICML 2024 · similarity 0.85)
- Toward the Goldilocks Blind Compression of Quantum States (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.