{"id":"93b1ef32-b5c6-4197-9ead-e32985476428","arxiv_id":"2607.29686","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Online shadow tomography can be solved with O(log m sqrt(log d)/eps^3) or O(sqrt(m)/eps^2) copies, matching known classical rates, but the first bound's key proof lemma contains an invalid inequality.","lead":"The paper proposes two quantum-state copy-count bounds for online shadow tomography that would match classical adaptive data analysis rates. One bound is dimension-free; the other depends logarithmically on dimension but its proof has a gap in a key damage-control lemma.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.9's Eq. (10) uses a reversed inequality; for the logistic f this bound fails sharply, so Corollary 4.6 and Theorem 1.2 are not established as written.","rationale":"I read the paper in good faith and agree with the reader's assessment. The central claim is that two protocols match the classical adaptive-data-analysis rates. The dimension-free protocol (Theorem 1.3) appears internally consistent: its per-step damage bound in Lemma 5.3 follows from Lemma 4.8 with F = 1 and the Fourier calculation in Claim 5.5, and the telescoping argument yields the claimed √m/ε² copy complexity. The logarithmic-in-m protocol (Theorem 1.2), however, rests on Corollary 4.6, whose proof contains a specific invalid inequality in Lemma 4.9, Eq. (10). The direction of the inequality is exactly backwards, and for the logistic function the failure is exponentially large. This is not a disagreement with a consensus or a matter of interpretation; it is an internal mathematical gap at a load-bearing point. The reader's weakest_assumption identifies precisely this step, and I see no other concern of comparable weight. I also noted a secondary algebra slip in the Corollary 4.6 proof: for the logistic f, α'√f = (λ/2)f√(1-f), not (λ/2)√(1-f); this overestimates L_f but still gives L_f ≤ λ/2, so it is less serious. A repair of Lemma 4.9 may be possible by replacing √f_+ with 1/√f_-, and the λ ≤ n assumption may keep the constant controlled, but the manuscript as written does not supply that repair. The verdict should remain CONDITIONAL: the result is plausible and the gap is local, but Theorem 1.2 is not established as written.","tokens_in":22607,"tokens_out":16403,"duration_ms":161828,"concrete_test":"Independently re-derive Lemma 4.9's block estimate without invoking Eq. (10). A direct numerical check: take f(x) = 1/(1+e^{-λ(x-b)}) with λ = n, b = 1, and I = [0, 1/n]. Then f_- = f(0) ≈ e^{-λ}, f_+ = f(1/n) ≈ e^{-λ(1-1/n)}, and Eq. (10)'s two sides are approximately (λ/2)√f_+ and (λ/2)f_+^{3/2}, so the asserted inequality fails by a factor of 1/f_+ = e^{λ(1-1/n)}. Then recompute Corollary 4.6 using the valid bound sup_I α' ≤ L_f/√f_- and R_f ≤ e^{λ/n}; if the final coefficient of (λ²/n²)Tr(Fτ) remains at most 2, Theorem 1.2 is repairable; if not, the logarithmic-in-m rate lacks a valid proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The logarithmic-in-m protocol depends entirely on the per-step damage bound Corollary 4.6, which is proved via Lemma 4.9. In Lemma 4.9, Eq. (10) asserts that ∆ ≤ (1/n)·√f_+ · sup_{x∈I}(α'(x)√f(x)). This inequality has the wrong direction: since √f(x) ≤ √f_+, one immediately gets sup_I(α'√f) ≤ √f_+ sup_I α', not the reverse. To control sup_I α' in terms of L_f = sup(α'√f), one must divide by the minimum value √f_- on the block, not multiply by √f_+. For the logistic f used in Corollary 4.6, this is not a small distinction: on a block where f_- is exponentially small, f_+ ≈ f_- e^{λ/n}, and sup_I α' ≈ (λ/2)√f_+ while L_f ≈ (λ/2)f_+, so Eq. (10) fails by a factor of about 1/f_+ = e^{λ/n}. Corollary 4.6's bound — that a soft binary measurement increases energy by at most (2λ²/n²)Tr(Fτ) — is the step that makes the telescoping argument in Lemma 4.7 go through; without it, the claimed n = O(√K log(m+K)/ε²) rate for Theorem 1.2 has no proof. The error is local and plausibly repairable: replacing √f_+ by 1/√f_- introduces extra factors of R_f = f_+/f_- ≤ e^{λ/n}, and the assumption λ ≤ n may still yield a constant below 2. But that repair is not present in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses Online Shadow Tomography, where an adversary adaptively chooses observables A^(t) and the learner estimates Tr(A^(t)ρ) from n copies of an unknown d-dimensional state ρ. It proposes two protocols and claims sample complexities n = O(√K log(m+K)/ε²) with K = Θ(log d/ε²) (Theorem 1.2) and n = O(√m/ε²) (Theorem 1.3), which match the classical adaptive-data-analysis rates. The technical framework is an 'excitation decomposition' of the n-copy state relative to a purification: the energy E[τ] = Tr(Nτ)/n is used to charge post-measurement damage. Section 5's dimension-free protocol uses a continuous POVM with compact cosine noise; Section 4's logarithmic-in-m protocol uses soft binary logistic measurements inside an MMW 'teacher-student' loop. The appendix gives an information-theoretic threshold-search result.","tokens_in":23079,"tokens_out":24949,"duration_ms":246339,"significance":"The claimed results, if established, would close the quantum-classical gap for online shadow tomography in all three parameters m, d, ε and would give the first o(log² m) online protocol with poly(log d/ε) dependence. Theorem 1.3 would also improve the previous dimension-free bound by a √m log m factor. The excitation-decomposition framework is a genuinely promising addition to the gentle-measurement toolbox, and the dimension-free half of the paper (Section 5) appears self-contained and correctly implemented. However, the logarithmic-in-m half has a specific proof gap described below, so the headline claim is not established as written.","major_comments":[{"comment":"The displayed inequality ∆ ≤ (1/n)·sup_I α′ ≤ (1/n)·√f_+ · sup_I(α′√f) has the wrong direction. Since √f(x) ≤ √f_+, one gets sup_I(α′√f) ≤ √f_+ · sup_I α′, not the reverse; equivalently, sup_I α′ ≥ sup_I(α′√f)/√f_+. For the logistic f used in Corollary 4.6 the failure is severe: on a block where f_+ is small, L_f = sup(α′√f) ≈ (λ/2)f_+ while sup α′ ≈ (λ/2)√f_+, so Eq. (10) overestimates the bound by roughly 1/f_+. Consequently Lemma 4.9's operator bound, Corollary 4.6, and the telescoping Lemma 4.7 do not follow. Since Lemma 4.7 is the only argument bounding ∑ E[τ] by O(λ²K/n²), Theorem 1.2 is not established as written. The error is local and a repair may be possible using the explicit logistic identity α′ = (λ/2)√(f/(1−f)) and the ratio f_+/f_-, but no such repair appears in the manuscript.","section":"§4.3, Lemma 4.9, Eq. (10)"}],"minor_comments":[{"comment":"The displayed identity α′(x)√f(x) = (λ/2)√(1−f(x)) is algebraically incorrect; the correct derivative is α′(x)√f(x) = (λ/2) f(x)√(1−f(x)). The claimed bound L_f ≤ λ/2 still holds because f√(1−f) ≤ 1/2, but the derivation as written is wrong.","section":"§4.3, proof of Corollary 4.6"},{"comment":"'Plancherel' should be 'Parseval' in the context of L² norm preservation, and the normalization convention for the Fourier transform should be stated explicitly. These are harmless presentation issues.","section":"§5.3, Claim 5.5"},{"comment":"The notation ∫_D Tr(τ_e) de for integration over the continuum tree is used before being formally defined. A short paragraph defining the measure on transcripts would improve readability.","section":"§5.2"},{"comment":"The repeat–until structure is understandable but slightly ambiguous when 'failed' is set inside the loop. Clarifying that the next iteration checks 'failed' first would help.","section":"Algorithm 1, line 19"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 4.9 is in the main-line Theorem 1.2, not a presentation issue, so I cannot recommend acceptance. I am recommending major revision rather than rejection because Section 5's dimension-free protocol appears sound and the logistic measurement has enough explicit structure that a repair of Lemma 4.9 seems plausible. The manuscript should not be accepted until Theorem 1.2 is reproven with a valid per-step damage bound. I did not factor the statement on AI use into the assessment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a serious paper with a real hole. The dimension-free protocol (Theorem 1.3) looks correct and is a clean improvement. The logarithmic-in-m protocol (Theorem 1.2) is not established as written—Lemma 4.9, Eq. (10) has the inequality backwards, and everything downstream depends on it.\n\nWhat's genuinely new: the claimed rates would close the gap to the classical adaptive-data-analysis rates in all three parameters. The excitation-decomposition accounting for post-measurement damage is a nice framework, and even if the logarithmic result falls, the framework plus the dimension-free protocol is a real advance. The Section 5 proof of Theorem 1.3 is self-contained and the lemmas trace correctly; the Fourier/POVM argument is sound.\n\nThe soft spot: Eq. (10) in Lemma 4.9 asserts Δ ≤ (1/n)√f_+ · sup(α'√f). Since √f ≤ √f_+, the sup of α'√f is bounded above by √f_+ sup α', not below; you need the minimum of √f on the block to go the other way. For the logistic f, on a block where f_- is tiny, this is not a factor-of-2 issue—it's off by e^{λ/n}. Corollary 4.6 and the telescoping in Lemma 4.7 rest on this step, so Theorem 1.2 has no proof as written. The repair looks plausible: use 1/√f_- and eat the factor R_f ≤ e^{λ/n}, and with λ ≤ n the constant might still be under the required 2. But that is not what the manuscript does.\n\nThe appendix on Best Observable Selection is a bit of a digression and doesn't feed into the main theorems; not a flaw, just odd in an already dense paper. The AI-use disclosure doesn't change the technical assessment.\n\nBottom line: worth a serious referee, not a desk reject. The main result is important, and the error is local and likely repairable. The referee should ask the authors to fix Lemma 4.9 and re-check the constants. If that goes through, this is a major paper.","headline":"Strong paper with a real gap: the dimension-free protocol holds up, but Theorem 1.2 relies on a faulty inequality in Lemma 4.9 that is likely fixable but not fixed.","tokens_in":23591,"tokens_out":3560,"would_cite":true,"duration_ms":37532,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Quantum online shadow tomography now matches classical sample rates in all parameters.","keywords":["online shadow tomography","quantum state learning","adaptive data analysis","quantum Efron-Stein decomposition","gentle measurements","sample complexity","post-measurement damage"],"falsifier":"Compute, for the logistic f(x)=1/(1+e^{lambda(b-x)}) with parameters from Theorem 1.2, the quantity L_f R_f(1+sqrt(R_f))/n in Lemma 4.9 and test whether sup_{x in I} alpha'(x) <= sqrt(f_+) sup_{x in I} alpha'(x) sqrt(f(x)) holds for every interval I of width at most 1/n. A single numerical counterexample to this inequality would invalidate the energy-increase bound as stated, and with it the current proof of Theorem 1.2.","tokens_in":22505,"feed_emoji":"⚛️","tokens_out":5076,"duration_ms":48803,"temperature":0.7,"pith_summary":"This paper tries to establish that Online Shadow Tomography—estimating the expectation values of an adaptively chosen sequence of quantum observables from copies of an unknown state—can be solved with the same number of copies as the classical problem of adaptive data analysis. The authors propose two protocols: one using O(log m sqrt(log d)/eps^3) copies, the other using O(sqrt(m)/eps^2) copies. If correct, these match the best known classical rates and close a gap that had been open in all three parameters m, d, and eps. The proofs rest on a new way to quantify how much a gentle measurement damages the state, based on the quantum Efron–Stein decomposition.","feed_headline":"Quantum online tomography now matches classical sample rates","feed_subtitle":"Two protocols need O(log m sqrt(log d)/eps^3) or O(sqrt m/eps^2) copies, closing a long gap.","key_machinery":"The key object is the excitation decomposition of the n-copy state |phi> = sum_{S subset [n]} |phi_S> where |phi_S> is the component with excitations on S, together with the energy E[tau] = (1/n) Tr(N tau) for the number operator N = sum_i (1 - |psi><psi|)_i. Lemma 3.4 bounds the probability of a 'bad' event by O(E[tau]/eps^2). The per-step damage controls (Corollary 4.6 and Lemma 5.3) bound the expected energy increase of a soft measurement: for the logistic measurement, O(lambda^2/n^2) Tr(F tau); for the compact-noise measurement, O(1/(n^2 eps^2)) Tr(tau).","core_discovery":"The central claim is that the sample complexity of Online Shadow Tomography matches the classical adaptive-data-analysis rates. Theorem 1.2 gives a protocol using n = O(sqrt(K) log(m+K)/eps^2) copies with K = Theta(log d/eps^2), i.e., n = O(log m sqrt(log d)/eps^3); Theorem 1.3 gives a protocol using n = O(sqrt m/eps^2) copies, independent of d. The authors prove these by tracking the 'energy' of the n-copy state under a decomposition into excitations relative to a purification of rho, and showing that each round's measurement increases this energy only in proportion to how likely the protocol is to make a mistake. The logistic-based soft measurement yields the logarithmic-in-m rate; a compa","pith_inferences":["The excitation-energy framework should extend to other adaptive quantum learning tasks where gentle measurements are used, such as online state certification or quantum channel learning, giving damage bounds in terms of a comparable 'influence' quantity.","The compact-noise protocol suggests a direct tradeoff: each measurement adds a fixed 'noise variance' to the state, so one might tune the noise width to control smoothness versus accuracy in other query models.","A natural testable extension is to replace the logistic function with a smoothed threshold kernel optimized for the damage bound, possibly removing the log(m+K) factor or reducing the eps-dependence in the logarithmic-in-m regime.","If the per-step damage bound fails as written, the logarithmic-in-m rate might still hold via a different per-step estimate; the framework itself may survive with a corrected inequality."],"forward_implications":["The quantum sample complexity for online shadow tomography now matches the classical adaptive data analysis rates in all parameters m, d, eps.","The O(log m sqrt(log d)/eps^3) protocol is the first online shadow tomography protocol with o(log^2 m) dependence together with poly(log d / eps) dependence.","The O(sqrt m/eps^2) protocol is optimal among dimension-independent protocols up to constants and improves the best prior dimension-independent bound by a sqrt(m) log m factor.","The same energy-accounting technique improves all three exponents even for the offline shadow tomography setting.","The proof gives a non-differential-privacy route to the classical adaptive data analysis rates, via Fourier analysis over product spaces."],"fun_headline_variants":["Online shadow tomography reaches classical sample rates","Quantum tomography now matches classical adaptive-data rates","Closing the gap to classical bounds in online shadow tomography","Two protocols match classical sample complexity in quantum tomography","Online shadow tomography optimal sample bounds achieved"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof of the logarithmic-in-m rate relies on the per-step damage bound (Corollary 4.6), whose derivation uses an inequality (Eq. (10) in Lemma 4.9) that may not hold for the logistic function; if that inequality cannot be repaired, the O(log m sqrt(log d)/eps^3) rate is not established as written.","fun_headline_variants_meta":{"raw":{"variants":["Online shadow tomography reaches classical sample rates","Quantum tomography now matches classical adaptive-data rates","Closing the gap to classical bounds in online shadow tomography","Two protocols match classical sample complexity in quantum tomography","Online shadow tomography optimal sample bounds achieved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000211,"raw_usage":{"total_tokens":1315,"prompt_tokens":875,"completion_tokens":440,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":373}},"tokens_in":619,"tokens_out":440,"duration_ms":4805,"temperature":1.0,"reasoning_tokens":373,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T01:49:19.363875+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for the logistic f(x)=1/(1+e^{lambda(b-x)}) with parameters from Theorem 1.2, the quantity L_f R_f(1+sqrt(R_f))/n in Lemma 4.9 and test whether sup_{x in I} alpha'(x) <= sqrt(f_+) sup_{x in I} alpha'(x) sqrt(f(x)) holds for every interval I of width at most 1/n. A single numerical counterexample to this inequality would invalidate the energy-increase bound as stated, and with it the current proof of Theorem 1.2.","supporting_citations":[],"review_version":1}