{"id":"bedbf3c6-27f4-454d-a70f-82cc544efda3","arxiv_id":"2608.05740","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves O(LB√T) regret for Projected Online Gradient Descent in online quantum state learning under bounded Frobenius norm measurements, with dimension-free corollaries for low-rank and sparse effects, and an O(log T) regret bound for Follow-the-Leader under squared L2 loss.","lead":"This paper analyzes online learning of quantum states and derives regret bounds for Projected Online Gradient Descent that depend on the Frobenius norm of the measurements, yielding dimension-free guarantees when measurements are low-rank or sparse. A generalist reader might care because these results suggest that structural assumptions, not just the size of the Hilbert space, control how efficiently quantum states can be learned in adversarial online settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Projection step: Claim 4.1 is false, so the proof of Lemma 4.2 is invalid; Algorithm 1's update is unproven as written.","rationale":"The reader's weakest_assumption is the bounded-Frobenius-norm condition, which is an applicability condition rather than a correctness threat. The reader's rationale separately flags the false Claim 4.1 and Lemma A.1, and the present stress-test agrees that the projection-lemma proof is the most load-bearing correctness gap for the main algorithm. The OGD regret theorem itself does not depend on Claim 4.1 or Lemma A.1, and its proof is a standard application of non-expansiveness of Euclidean projection and bounded gradients. Since Lemma 4.2 is known to be true and can be proved without Claim 4.1, the appropriate disposition is a conditional acceptance requiring the authors to correct or properly cite the projection characterization. This matches the reader's CONDITIONAL verdict, so no verdict adjustment is needed.","tokens_in":9419,"tokens_out":21605,"duration_ms":188448,"concrete_test":"Test Claim 4.1 and Lemma 4.2 on a small example: set P = diag(2,1,-10) in dimension 3, compute the Euclidean projection of (2,1,-10) onto the probability simplex via soft-thresholding, and compare supports. The positive part of P has support {1,2} while the projected density matrix has support {1}, so Claim 4.1 is false. Then independently minimize ||Q-P||_F^2 over Q ⪰ 0 with tr(Q)=1 using Ky Fan's inequality; the optimum is diagonal in P's eigenbasis with soft-thresholded eigenvalues, recovering Eq. (4). This confirms that Lemma 4.2 is true and isolates the flaw to the proof of Lemma 4.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central OGD regret bound in Theorem 4.5 is a standard projected-gradient argument and appears correct. The load-bearing gap is in the projection step that defines Algorithm 1. Claim 4.1 asserts supp(P_+) = supp(Π_{D(X)}(P)) for the Frobenius projection. This is false: for P = diag(2,1,-10), P_+ has support {1,2}, while the projection onto the simplex, using the soft-threshold formula in Lemma 4.2 with μ = 1, gives z = (1,0,0), whose support is {1}. Lemma 4.2 itself is the correct characterization of the Frobenius projection onto density matrices, but its proof in the paper invokes the false Claim 4.1, so the proof is invalid. Because Algorithm 1's update and Observation 2.2's O(d^ω) complexity claim both rely on Lemma 4.2, the paper as written does not establish that the algorithm it analyzes can be implemented as claimed. The fix is straightforward: replace the argument with the standard eigenvector-alignment proof or cite [GGRL16]. This is a proof-hygiene issue rather than a refutation of the regret bound, but it is the point at which the central construction is least secure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9580,"tokens_out":10108,"duration_ms":90830,"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":[{"comment":"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.","section":"Section 4.1, Claim 4.1 and Lemma 4.2"},{"comment":"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.","section":"Appendix A, Lemma A.1 and regret expansion"}],"minor_comments":[{"comment":"The phrase 'Summing the inequality in Theorem 4.4' should refer to Claim 4.4, not to a theorem.","section":"Proof of Theorem 4.5"},{"comment":"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.","section":"Theorem 4.5"},{"comment":"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.","section":"Corollary 2.4"},{"comment":"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.","section":"Observation 2.2"}],"recommendation":"major_revision","confidential_remarks":"The core OGD regret bound is sound as an oracle-based statement, but the manuscript's two proof gaps are exactly the kind of load-bearing issues that must be fixed before publication. Both have standard fixes, so major revision is appropriate rather than rejection. I would also ask the authors to state more prominently that the dimension-free guarantee is only an improvement over [ACH+18] when the Frobenius parameter B is small relative to the ambient dimension."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nOne 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.\n\nBottom 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.","headline":"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.","tokens_in":10196,"tokens_out":6835,"would_cite":false,"duration_ms":55328,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","90C25"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"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.","keywords":["online learning","quantum state tomography","regret bounds","online gradient descent","low-rank measurements","sparse measurements","shadow tomography","logarithmic regret"],"falsifier":"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.","tokens_in":1985,"feed_emoji":"⚛️","tokens_out":2571,"duration_ms":87768,"temperature":0.7,"pith_summary":"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.","feed_headline":"Online quantum learning: regret O(LB√T), no qubit factor","feed_subtitle":"Structured measurements, low rank or sparse, make the bound O(L√(rT)); the quadratic-loss variant hits O(log T).","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the online quantum state learning problem and gives the general $O(L\\sqrt{nT})$ regret baseline that this paper improves.","marker":"[ACH+18]"},{"why":"Supplies the Projected Online Gradient Descent algorithm and the standard one-step regret analysis used in Theorem 4.5.","marker":"[Haz16]"},{"why":"Provides the Follow-the-Leader lemma on which the logarithmic regret for squared $L_2$ loss rests.","marker":"[Ora19]"},{"why":"Offers an independent treatment of Frobenius-norm projection onto density matrices, supporting the projection step used by OGD.","marker":"[GGRL16]"},{"why":"Gives the earlier low-rank regret bound that Corollary 2.3 recovers and generalizes.","marker":"[CW20]"},{"why":"Supplies the batch shadow-tomography sample-complexity lower bound cited to argue that the Frobenius parameter is statistically meaningful.","marker":"[HKP20]"},{"why":"Previous OGD-type analysis for online quantum state learning that the paper says Theorem 4.5 tightens.","marker":"[YJZS20]"}],"fun_headline_variants":["Online quantum learning: regret depends on measurement norm, not dimension","Structured measurements make online quantum state learning regret O(LB√T)","Logarithmic regret for online quantum state learning with squared loss","Rank and sparsity improve regret in online quantum state learning","Quantum state online learning: from √T regret to log T"],"cache_read_input_tokens":12288,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Online quantum learning: regret depends on measurement norm, not dimension","Structured measurements make online quantum state learning regret O(LB√T)","Logarithmic regret for online quantum state learning with squared loss","Rank and sparsity improve regret in online quantum state learning","Quantum state online learning: from √T regret to log T"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001006,"raw_usage":{"total_tokens":4270,"prompt_tokens":976,"completion_tokens":3294,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":3207}},"tokens_in":592,"tokens_out":3294,"duration_ms":22743,"temperature":1.0,"reasoning_tokens":3207,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:36:32.546123+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}