Improved regret bounds for structured online learning of quantum states

Akshay Bansal; Jiahui Liu

REVIEW 2 major objections 4 minor 31 references

Improved regret bounds for structured online learning of quantum states

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Online learning of quantum states becomes dimension-free when adversarial measurements have bounded Frobenius norm: projected online gradient descent achieves regret at most $2LB\sqrt{T}$, independent of qubit count.

desk verdict The main OGD regret bound is correct and the sparsity corollary is new, but two supporting lemmas are false and the log-regret proof is broken—worth a careful revision, not a desk reject. read the letter →

arxiv 2608.05740 v1 pith:7TC4RQEX submitted 2026-08-06 quant-ph

Akshay Bansal , Jiahui Liu This is my paper · ORCID

classification quant-ph MSC 81P6868Q1290C25 PACS 03.67.-a

keywords onlinelearningquantumstatetomographyregretboundsgradientdescentlow-rankmeasurementssparseshadowlogarithmic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that online learning of quantum states, where a learner predicts measurement outcomes round by round against an adaptive adversary, becomes much easier when the measurements are structured. It analyzes Projected Online Gradient Descent and proves regret at most $2LB\sqrt{T}$ when each adversarial measurement operator has Frobenius norm at most $B$, with no dependence on the number of qubits. When the measurements are low rank or sparse, the bound becomes $O(L\sqrt{rT})$ or $O(L\sqrt{\kappa T})$, beating the general $O(L\sqrt{nT})$ guarantee. The paper also shows that in a multi-outcome squared-$L_2$ setting, the simple averaging strategy achieves regret $O(\log T)$, again independent of qubits and outcome count. A sympathetic reader would care because these results replace the ambient Hilbert-space dimension with intrinsic structural parameters in the regret bound.

What carries the argument

The load-bearing mechanism is the one-step OGD progress inequality combined with a bound on the gradient of the loss in Frobenius norm. Since the loss at round $t$ is $\ell_t(\operatorname{tr}(E_t\omega_t))$, the gradient is $\nabla_t = \ell_t'(\operatorname{tr}(E_t\omega_t)) E_t$, and Lipschitzness plus $\lVert E_t\rVert_F \le B$ give $\lVert \nabla_t\rVert_F \le L B$. Telescoping the non-expansiveness of the Euclidean projection onto the set of quantum states yields $D^2/(2\eta) + \eta T L^2 B^2/2$, and choosing $\eta = D/(LB\sqrt{T})$ gives $D L B \sqrt{T}$. The projection itself reduces to a spectral decomposition plus a Euclidean projection onto the simplex, so each update costs $O(d^\omega)$. For the logarithmic result, the mechanism is Follow-the-Leader with a quadratic loss: the optimal prediction is the empirical mean of the revealed outcome vectors, and successive means move by at most $2B/t$, making the total movement a harmonic sum.

What would settle it

Run Projected Online Gradient Descent with its optimal step size against an adversarial sequence in which every effect $E_t$ is the projector onto a fixed random half-dimensional subspace, so $\lVert E_t\rVert_F = 2^{(n-1)/2}$, and every loss is linear with $L=1$. If the realized regret grows like $2^{n/2}\sqrt{T}$, then the dimension-free claim is false without the $B$-boundedness premise; if instead the regret stays $O(\sqrt{T})$, then the measurements carry genuine structure that makes the problem easier than the Frobenius-norm bound suggests.

Watch

Extended reading notes

Core claim

The paper's central claim is that the online learnability of quantum states is governed by a geometric parameter of the adversary's measurement operators, their Frobenius norm $B$, rather than by the dimension $2^n$ of the state space, whenever the loss is convex and $L$-Lipschitz. Concretely, Theorem 4.5 gives regret $R_T \le D L B \sqrt{T}$ for Projected Online Gradient Descent, with $D\le 2$, hence $R_T \le 2 L B \sqrt{T}$. Since rank-$r$ effects have Frobenius norm at most $\sqrt{r}$ and $\kappa$-sparse effects at most $\sqrt{\kappa}$, this yields $R_T = O(L\sqrt{\min\{r,n\}T})$ and $R_T = O(L\sqrt{\min\{\kappa,n\}T})$, recovering the earlier low-rank guarantee and extending it to sparsity and other structured effects. In the $K$-outcome squared-$\ell_2$ setting, the averaging Follow-the-Leader strategy attains regret $R_T = O(\log T)$, independent of $n$ and $K$, because successive empirical means move by at most $O(B/t)$.

Load-bearing premise

The result's improvement over prior bounds collapses unless the adversary's measurement operators have a Frobenius norm $B$ that is small compared to $\sqrt{d} = 2^{n/2}$; if $B$ grows with dimension, the stated $O(LB\sqrt{T})$ regret is no better than the existing $O(L\sqrt{nT})$ guarantee.

Editorial extensions

If this is right

For rank-$r$ adversarial measurements, regret is $O(L\sqrt{\min\{r,n\}T})$, so online shadow tomography can be exponentially cheaper than general state learning when $r$ is small.
For $\kappa$-sparse measurements, the same guarantee $O(L\sqrt{\min\{\kappa,n\}T})$ applies, covering compressed-sensing-style and Pauli-basis structured effects.
Each OGD iterate costs $O(d^\omega)$ with $\omega \le 2.37$, so the improved regret does not come with extra computational overhead relative to regularized follow-the-leader updates.
Under squared $L_2$ loss with $K$-outcome measurements, regret is $O(\log T)$ independent of $n$ and $K$, so a learner can track all outcome probabilities with negligible per-round regret.
The $\sqrt{T}$ dependence is unavoidable for general convex Lipschitz losses, so the qualitative rate cannot be improved; the parameters $B$, $r$, and $\kappa$ are the remaining quantities to optimize.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The Frobenius-norm parameter $B$ is what makes the dimension-free claim meaningful: low rank or sparsity must actually be reflected in a small operator norm. For a projector onto a $d/2$-dimensional subspace, $B = \sqrt{d/2}$, and the OGD bound is exponentially worse than the standard $O(L\sqrt{nT})$ bound, so the improvement is real exactly when the measurements are concentrated on few degrees of
The logarithmic bound suggests that for prediction of outcome vectors, the relevant complexity is the concentration or variance of the outcome vectors $b_t$, not the underlying Hilbert-space dimension; analogous $O(\log T)$ guarantees likely hold for other strongly convex losses, and for bandit feedback at the price of an extra factor depending on the number of outcomes.
A matching online lower bound in $B$, such as $\Omega(LB\sqrt{T})$, would tie the online regret to the batch shadow-tomography sample complexity and would confirm that the Frobenius norm, not the dimension, is the right hardness parameter; the paper notes that such a lower bound is still open.
The simplex-projection view of the density-matrix projection means the expensive step is only diagonalizing a $d\times d$ Hermitian matrix, which may make online quantum-state learning practical at moderate system sizes.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read this one with a red pen. The headline result is fine, the packaging overstates, and two of the supporting lemmas are simply false as written. The main regret bound in Theorem 4.5—projected OGD with bounded-Frobenius measurements gives R_T ≤ O(L B √T)—is a clean, correct application of standard online convex analysis. The sparsity corollary (R_T ≤ O(L √(κ T))) is genuinely new as far as I can tell; the low-rank version is properly credited to [CW20]. The paper also does the right thing by acknowledging the known Frobenius-projection result in [GGRL16] after presenting its own proof.

The soft spots are real and load-bearing. Claim 4.1 is false: the support of the positive part of a Hermitian matrix need not match the support of its Frobenius projection onto density matrices. The example in the stress-test note works—diag(2,1,-10) projects to diag(1,0,0)-type support, not diag(2,1,0). Because Lemma 4.2 relies on that claim, its proof is not valid, even though the lemma itself is true and known. That matters because Algorithm 1's update is exactly this projection, so the paper as written doesn't actually prove its own algorithm can be implemented. The fix is easy: cite [GGRL16] or use the standard eigenvector-alignment argument. But it is a hole.

The appendix is worse. Lemma A.1 is false as stated; the sum of losses at the leaders is not bounded by the loss of the final leader. The subsequent FTL regret proof in the Appendix A is correspondingly broken; the first displayed regret expansion compares to y_t rather than to the fixed comparator, so the algebra doesn't establish the claimed O(log T) regret. I suspect the log-regret result is true—the mean predictor for bounded vectors in Euclidean space does give O(log T) regret—but the paper's proof needs to be redone with the standard be-the-leader or FTL stability argument.

One minor: the paper says the Frobenius diameter of the density matrices is at most 2; the tight value is √2, which only makes the bound slightly better.

Bottom line: the main structural idea is sound and the low-rank/sparsity message is worth publishing once the projection lemma and the FTL analysis are fixed or replaced by proper citations. This is a paper for a serious referee, not a desk reject, but I would send it back for a revision rather than accept anything close to the current form.

Referee Report

2 major / 4 minor

Summary. The paper studies online learning of quantum states in the adversarial setting of Aaronson et al. (ACH+18). For losses of the form ℓ_t(tr(E_t ω_t)) with convex L-Lipschitz scalar losses and measurement operators E_t satisfying ∥E_t∥_F ≤ B, it analyzes Projected Online Gradient Descent and proves a regret bound R_T ≤ D L B √T (Theorem 4.5), from which it derives low-rank and sparse corollaries. It also claims an O(log T) regret bound for K-outcome measurements under squared L2 loss using a Follow-the-Leader/averaging algorithm. The OGD regret argument itself is a standard projected-gradient analysis and is essentially correct if an exact projection oracle is available; however, the proof of the projection lemma in Section 4.1 rests on a false claim, and the Appendix A proof of the logarithmic-regret result contains a false lemma and an incorrect regret expansion.

Significance. If the identified gaps are repaired, the paper's main contribution is useful and interesting. Theorem 4.5 is a clean, dimension-free structural regret bound with explicit assumptions and no fitted parameters, and the low-rank corollary recovers and generalizes the earlier bound of Chen and Wang (CW20) via a different algorithm. The paper also honestly discusses the limitation that the Frobenius-norm improvement is only meaningful when B itself is small, not when the effects are unstructured. The projection lemma is a known standard result, and the logarithmic regret claim for quadratic losses is plausible, so the flaws are local and fixable rather than fatal to the overall approach.

major comments (2)

[Section 4.1, Claim 4.1 and Lemma 4.2] Claim 4.1 is false: for P = diag(2,1,-10), the positive part P_+ has support {1,2}, while the Frobenius projection onto D(X) given by the soft-threshold formula in Lemma 4.2 with μ=1 is diag(1,0,0), whose support is {1}. Since the proof of Lemma 4.2 invokes Claim 4.1, the justification of the projection formula, and hence the implementation claim for Algorithm 1 and the O(d^ω) complexity claim in Observation 2.2, is invalid as written. Lemma 4.2 itself is a standard result and can be proved directly from unitary invariance of the Frobenius norm, or by citing [GGRL16]; the proof should be replaced rather than the lemma.
[Appendix A, Lemma A.1 and regret expansion] Lemma A.1 is false in general. For example, take ℓ_1(x)=(x−1)^2, ℓ_2(x)=0, y_1=0, y_2=1, and x_T=1; then ∑_{t=1}^2 ℓ_t(y_t)=1 while ∑_{t=1}^2 ℓ_t(x_T)=0. Moreover, the displayed expansion of R_T compares x_t to the time-dependent FTL iterate y_t, whereas the true regret compares x_t to the fixed minimizer y_T of the cumulative loss. The resulting bound on ∑∥y_t−y_{t-1}∥ controls prediction stability, not the stated regret, so Proposition 2.5's O(log T) claim is not established by the argument given. A standard FTL stability analysis may well prove the claim, but the current proof needs a substantial repair.

minor comments (4)

[Proof of Theorem 4.5] The phrase 'Summing the inequality in Theorem 4.4' should refer to Claim 4.4, not to a theorem.
[Theorem 4.5] The Frobenius diameter of D(X) is √2, not 2; the bound with D=2 is valid but unnecessarily loose, and the final constant can be improved to R_T ≤ √2 L B √T.
[Corollary 2.4] The κ-sparse assumption should specify the basis in which sparsity is measured; the bound B ≤ √κ is immediate for computational-basis sparsity but requires a brief justification for other bases.
[Observation 2.2] The comparison 'at least as good as RFTL' is informal; RFTL with von Neumann entropy also requires matrix exponentiation at comparable O(d^ω) cost, so the statement should be made precise or softened.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: OGD regret bound follows from the stated Lipschitz and Frobenius-norm assumptions; no fitted parameter or self-citation is load-bearing.

full rationale

Walking the derivation chain, the central bound in Theorem 4.5 is a standard projected-gradient telescoping argument. Its two inputs are the convexity/L-Lipschitz assumption on each loss and the bound ||E_t||_F <= B; neither quantity is fitted to the regret data, and the bound R_T <= D L B sqrt(T) is obtained by optimizing eta, not by invoking a prior result with the same conclusion. The projection lemma (Lemma 4.2) is derived from a spectral-decomposition reduction, and the paper explicitly credits an independent earlier treatment to [GGRL16]; it is therefore not an ansatz smuggled in by citation. Corollaries 2.3 and 2.4 follow by combining Theorem 4.5 with the independent general bounds of [ACH+18], and the low-rank bound is credited to [CW20] rather than to the authors' own work. The multi-outcome logarithmic-regret result in Appendix A is a standard FTL/averaging analysis for quadratic losses, with no self-referential step. The only notable issue found in the manuscript is the proof of Lemma 4.2: the proof sketch of Claim 4.1 appears to assert support equality that is not established, so the proof of Lemma 4.2 is not fully rigorous as written. But that is a correctness and proof-hygiene concern, not a circularity one: the lemma's statement is independently supported by [GGRL16] and does not assume the theorem it is used to prove. No expression in the paper is defined in terms of a target prediction, no fitted parameter is renamed as a prediction, and no load-bearing result is justified solely by a self-citation.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central results rest on standard online convex optimization facts (non-expansive projections, gradient bounds for Lipschitz functions, OGD progress inequality, Follow-the-Leader stability) and on the domain assumptions of bounded Frobenius norm effects and full-information probability-vector feedback. No parameters are fitted to data, and no new entities are postulated. The Frobenius projection characterization (Lemma 4.2) is imported from [GGRL16] and is not correctly proved in the paper because Claim 4.1 is false.

assumptions (6)

standard math Euclidean (Frobenius) projections onto convex sets are non-expansive: ∥Π(x)−Π(y)∥_F ≤ ∥x−y∥_F.
Used in Claim 4.4 (one-step progress inequality) and Theorem 4.5, the standard OGD analysis.
standard math A convex L-Lipschitz function on a normed space has subgradients with dual norm at most L.
Proposition 4.3; used to bound the gradient norm of the loss in Theorem 4.5.
domain assumption The Frobenius projection of a Hermitian matrix onto the set of density matrices is obtained by projecting its eigenvalue vector onto the probability simplex.
Lemma 4.2, the basis of the OGD update. The paper's proof references the false Claim 4.1, but the result is known from [GGRL16].
domain assumption Measurement operators are positive semidefinite with E_t ⪯ I and bounded Frobenius norm ∥E_t∥_F ≤ B.
Drives the gradient bound in Theorem 4.5 and the rank and sparsity corollaries.
domain assumption Loss functions ℓ_t: R → R are convex and L-Lipschitz.
Inherited from [ACH+18]; enables the OGD regret analysis.
domain assumption In the multi-outcome setting, the adversary reveals the full outcome probability vector b_t (full information) and ∥b_t∥_2 ≤ B.
Needed for the averaging strategy and the O(log T) bound; this is not the sample-feedback model of standard shadow tomography.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved regret bounds for structured online learning of quantum states." pith.science (2026). https://pith.science/paper/7TC4RQEX

@misc{pith2026260805740,
  author       = {Pith},
  title        = {Pith review of: Improved regret bounds for structured online learning of quantum states},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7TC4RQEX}},
  note         = {Machine review of arXiv:2608.05740}
}

abstract

Quantum state tomography is fundamental to quantum information processing but becomes infeasible at scale due to the exponential growth of the state space. Shadow tomography alleviates this challenge by focusing on predicting measurement outcomes rather than reconstructing the full state. Its online variant models adaptive and potentially adversarial measurement scenarios, where a learner sequentially predicts outcomes while competing with the best fixed quantum state in hindsight. We show that exploiting additional structure in the measurements leads to significantly stronger regret guarantees. In particular, under the assumption that the adversarial measurements have bounded Frobenius norm, we analyze Projected Online Gradient Descent and derive regret bounds that depend on intrinsic structural properties, such as rank or sparsity, rather than the ambient Hilbert space dimension. As a complementary result, we show that one can achieve logarithmic regret, independent of both the number of qubits and measurement outcomes, for multi-outcome measurements under squared $L_2$ loss. These results demonstrate that incorporating realistic structural assumptions can substantially enhance the learnability of quantum states in online environments.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

[1]

Nature Reviews Physics , volume=

A survey on the complexity of learning quantum states , author=. Nature Reviews Physics , volume=. 2024 , publisher=

work page 2024
[2]

Online Learning of Quantum States , volume =

Aaronson, Scott and Chen, Xinyi and Hazan, Elad and Kale, Satyen and Nayak, Ashwin , booktitle =. Online Learning of Quantum States , volume =

work page
[3]

Suthan Chittoor, Hari Hara and Simeone, Osvaldo and Banchi, Leonardo and Pirandola, Stefano , booktitle=. Online. 2023 , volume=

work page 2023
[4]

2020 , eprint=

Adaptive Techniques in Practical Quantum Key Distribution , author=. 2020 , eprint=

work page 2020
[5]

and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =

Haah, Jeongwan and Harrow, Aram W. and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =. 2016 , booktitle =

work page 2016
[6]

Vazirani , title =

Noam Nisan and Tim Roughgarden and Éva Tardos and Vijay V. Vazirani , title =. 2007 , publisher =

work page 2007
[7]

2016 , volume =

Foundations and Trends in Optimization , title =. 2016 , volume =

work page 2016
[8]

arXiv preprint arXiv:1912.13213 , year=

A modern introduction to online learning , author=. arXiv preprint arXiv:1912.13213 , year=

arXiv 1912

Show all 31 references

[9]

npj Quantum Information , volume=

Reinforcement learning with neural networks for quantum feedback , author=. npj Quantum Information , volume=
[10]

Learning

Gong, Weiyuan and Aaronson, Scott , booktitle =. Learning. 2023 , volume =

2023
[11]

arXiv preprint arXiv:2403.09968 , year=

Online learning for quantum state tracking with shadow tomography , author=. arXiv preprint arXiv:2403.09968 , year=

arXiv
[12]

Neural-network-assisted quantum state and process tomography using limited data sets , author =. Phys. Rev. A , volume =
[13]

Ghosh, Kalpak and Kumar, Sumit and Rajan, Nirmal Mammavalappil and Yamijala, Sharma S. R. K. C. , title =. ACS Omega , volume =
[14]

Neural-network-encoded variational quantum algorithms , author =. Phys. Rev. Appl. , volume =
[15]

npj Computational Materials , volume=

Autonomous reinforcement learning agent for chemical vapor deposition synthesis of quantum materials , author=. npj Computational Materials , volume=
[16]

2018 , booktitle =

Aaronson, Scott , title =. 2018 , booktitle =

2018
[17]

Optimization Methods and Software , volume=

A projected gradient method for optimization over density matrices , author=. Optimization Methods and Software , volume=. 2016 , publisher=

2016
[18]

Scalable Evaluation of Quantum-Circuit Error Loss Using Clifford Sampling , author =. Phys. Rev. Lett. , volume =
[19]

Advanced Quantum Technologies , volume =

Kuzmin, Viacheslav and Somogyi, Wilfrid and Pankovets, Ekaterina and Melnikov, Alexey , title =. Advanced Quantum Technologies , volume =
[20]

Flying-cat parity checks for quantum error correction , author =. Phys. Rev. Res. , volume =
[21]

Quantum , volume=

High-performance repetition cat code using fast noisy operations , author=. Quantum , volume=
[22]

Journal of Mathematical Physics , volume =

Spehner, Dominique , title =. Journal of Mathematical Physics , volume =
[23]

Quantum State Tomography via Compressed Sensing , author =. Phys. Rev. Lett. , volume =
[24]

Flammia, Steven T and Gross, David and Liu, Yi-Kai and Eisert, Jens , journal=. Quantum
[25]

Foundations and Trends in Machine Learning , volume=

Online learning and online convex optimization , author=. Foundations and Trends in Machine Learning , volume=
[26]

arXiv preprint arXiv:2006.01013 , year=

More Practical and Adaptive Algorithms for Online Quantum State Learning (2020) , author=. arXiv preprint arXiv:2006.01013 , year=

2020 arXiv
[27]

Proceedings of the AAAI Conference on Artificial Intelligence , volume=

Revisiting online quantum state learning , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
[28]

Nature Physics , volume=

Predicting many properties of a quantum system from very few measurements , author=. Nature Physics , volume=. 2020 , publisher=

2020
[29]

Examples of conditional

Ohno, Hiromichi and Petz, D. Examples of conditional. Quantum Information Processing , volume=. 2015 , publisher=

2015
[30]

PRX Quantum , volume =

Experimental Single-Setting Quantum State Tomography , author =. PRX Quantum , volume =
[31]

1968 , publisher=

Information theory and reliable communication , author=. 1968 , publisher=

1968

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Nature Reviews Physics , volume=

A survey on the complexity of learning quantum states , author=. Nature Reviews Physics , volume=. 2024 , publisher=

work page 2024

[2] [2]

Online Learning of Quantum States , volume =

Aaronson, Scott and Chen, Xinyi and Hazan, Elad and Kale, Satyen and Nayak, Ashwin , booktitle =. Online Learning of Quantum States , volume =

work page

[3] [3]

Suthan Chittoor, Hari Hara and Simeone, Osvaldo and Banchi, Leonardo and Pirandola, Stefano , booktitle=. Online. 2023 , volume=

work page 2023

[4] [4]

2020 , eprint=

Adaptive Techniques in Practical Quantum Key Distribution , author=. 2020 , eprint=

work page 2020

[5] [5]

and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =

Haah, Jeongwan and Harrow, Aram W. and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =. 2016 , booktitle =

work page 2016

[6] [6]

Vazirani , title =

Noam Nisan and Tim Roughgarden and Éva Tardos and Vijay V. Vazirani , title =. 2007 , publisher =

work page 2007

[7] [7]

2016 , volume =

Foundations and Trends in Optimization , title =. 2016 , volume =

work page 2016

[8] [8]

arXiv preprint arXiv:1912.13213 , year=

A modern introduction to online learning , author=. arXiv preprint arXiv:1912.13213 , year=

arXiv 1912