{"id":"766b1524-c24a-4821-bcab-a694ae96289c","arxiv_id":"2412.03381","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Applying Minsker's tighter median-of-means estimator with incomplete U-statistics to classical shadows improves sample efficiency for Clifford measurements but not for Pauli measurements.","lead":"This paper tests a statistically tighter version of the median-of-means estimator, due to Minsker, inside the classical shadows protocol for estimating quantum state properties. The new estimator helps for global Clifford measurements but not for single-qubit Pauli measurements, where the simpler original estimator still wins.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Clifford-measurement advantage of MomRand/MomCyc over Mom is never compared at matched k; Appendix C shows k, not estimator type, drives Pauli-measurement performance, and no analogous control is provided for the GHZ claim.","rationale":"The paper makes two distinct contributions: (i) a practical implementation of Minsker's median-of-means estimator via incomplete U-statistics (random and cyclic designs) with ARE calculations in Section II.D, and (ii) an empirical benchmarking claim that the modified estimators beat standard MoM for Clifford measurements. The first contribution is solid: the algorithms are concrete, the ARE formulas (29) and (32) are derived from Lee's variance identities, and the bound constants sqrt(2) versus sqrt(pi) are correctly imported. The second, headline contribution rests on an uncontrolled comparison. What would have to be true for the claim to hold is that the observed Mom-versus-MomRand/MomCyc gap in the GHZ fidelity experiments is due to the estimator structure (combination averaging before the median) rather than to the different k, l, and m regime in which the modified estimators operate. This condition is exactly what Appendix C shows fails in the Pauli setting: 'rather than the type of estimator used, the error depends most heavily on the number of groups k.' Because the authors never present the analogous k-sweep for Clifford measurements, and because they do not explicitly report k, l, and m for the GHZ runs, the alternative explanation remains live. The within-family inversion (MomCyc has higher ARE yet worse empirical performance than MomRand) further undercuts the theoretical attribution. I therefore agree with the reader's weakest_assumption; no stronger or more load-bearing concern surfaced. Two secondary points I considered but did not elevate: the o(1) factors in Theorems 1 and 2 are dropped with the comment 'we will ignore this factor' at k as small as 43, so the plotted 'bounds' are asymptotic and not rigorous at the simulated sample sizes; and the shadow subsampling procedure (sampling N snapshots from a fixed 50000-snapshot shadow) induces correlations across the N-sweep, which the 100-run averaging does not remove. Neither is as central as the k confound, since the headline is an empirical claim, not a claim about the rigor of the bounds. The practical utility of the paper is not destroyed: the incomplete-U-statistic implementations are a genuine contribution and the Clifford curves may well survive a matched-k test. But the specific sentence 'Mom now had higher error and variance than MomRand and MomCyc. This shows that Minsker's estimator offers an advantage' cannot be accepted as demonstrated until the matched-k experiment is run. CONDITIONAL is the right verdict, so I recommend no change to the reader's assessment.","tokens_in":25505,"tokens_out":7504,"duration_ms":64100,"concrete_test":"Reproduce the GHZ/Clifford fidelity benchmark (Figures 4-5, r = 2 and r = 5, 10, 15, 20; N = 1000 to 50000; M = 50, delta = 0.001) with k matched across estimators: run Mom at k = 65, 100, 150, 219 (the range Appendix C assigns to MomRand/MomCyc) and run MomRand/MomCyc at k = 43 (Mom's value), keeping l = log(N/k) and m = 10kl as in the methods. If the Mom-versus-MomRand/MomCyc gap closes or reverses under matched k, the headline advantage is a hyperparameter artifact; if MomRand/MomCyc still dominate at k = 43 and Mom at k = 219 does not reach them, the estimator-type advantage survives. Also report a Clifford analog of Figure 13 (error versus k for each estimator) so the k-dependence is explicit.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the empirical superiority of MomRand/MomCyc over Mom for Clifford (GHZ) fidelity estimation, interpreted as evidence that Minsker's estimator outperforms traditional MoM. The comparison is confounded by the number of groups k, and this confound is acknowledged by the authors for the Pauli setting but never controlled in the Clifford setting. Under the parameter choices stated in Section II.C (M = 50, delta = 0.001, t = k/log(k) for Mom; t = log(3M/delta), l = log(N/k) for the modified estimators), Mom runs with k = 43 for all N, while MomRand and MomCyc run with k in [65, 219] as N goes from 1000 to 50000 (Appendix C). The Clifford runs use the same recipe, so Mom is never compared with the modified estimators at the same k, hence not at the same number of median candidates or the same group size. Appendix C explicitly concludes for Pauli measurements that 'rather than the type of estimator used, the error depends most heavily on the number of groups k' and Figure 13 shows error increasing with k; the analogous k-sweep for the Clifford fidelity experiments, where the headline advantage is claimed, is absent. Additionally, the theoretical machinery does not predict the observed ordering even within the modified family: MomCyc has higher ARE than MomRand (Section II.D) yet performs worse empirically, so attributing the Mom-versus-MomRand gap to 'Minsker's estimator' rather than to the k, l, and m hyperparameters is unsupported without a matched-k, matched-m experiment.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper applies Minsker's improved median-of-means (MoM) estimator with sharp constants to the classical shadows protocol, introducing two practical incomplete U-statistic implementations (MomRand via random sampling, and MomCyc via cyclically permuted sampling) to make the estimator computationally feasible. It benchmarks these estimators against the standard median-of-means estimator for Pauli measurements on a transverse-field Ising chain and Clifford measurements on GHZ states, reporting that the modified estimators outperform the original for Clifford measurements while underperforming for Pauli measurements. The paper also compares numerical errors against the theoretical bounds of Minsker and Huang et al., and discusses the practical reduction in shadow size implied by the tighter constants.","tokens_in":25849,"tokens_out":6821,"duration_ms":60270,"significance":"If the Clifford-measurement advantage were established under controlled conditions, the paper would make a useful practical point: tighter constants in MoM bounds can reduce the required number of shots, and the choice of estimator should be tailored to the measurement ensemble. The two implementations of Minsker's estimator via incomplete U-statistics are a useful contribution, and the direct numerical comparisons provide concrete evidence. However, the central claim is currently confounded by the number of groups k, a confound the authors explicitly identify in Appendix C for the Pauli case but do not control in the Clifford case. The theoretical bounds are asymptotic, and the o(1) terms are ignored at the simulated sample sizes. The internal inconsistency between the theoretical ARE ordering and the empirical ordering of MomCyc versus MomRand further weakens the attribution of the observed advantage to the estimator type rather than to the hyperparameters.","major_comments":[{"comment":"The central claim that MomRand and MomCyc outperform Mom for Clifford measurements is not controlled for the number of groups k. The paper's own Appendix C concludes for Pauli measurements that 'rather than the type of estimator used, the error depends most heavily on the number of groups k' and shows in Figure 13 that error increases with k. The Clifford experiments in Section II.F use the same k recipe as the Pauli experiments: Mom uses k=43 for all N, while MomRand and MomCyc use k in [65, 219] as N goes from 1000 to 50000 (per Appendix C). No equivalent k-sweep is provided for the Clifford fidelity estimation. Consequently, the observed advantage of MomRand/MomCyc over Mom in Figures 4 and 5 may be a hyperparameter artifact rather than evidence that Minsker's estimator is intrinsically better. This confound is load-bearing because the paper's conclusion in Section III explicitly attributes the gap to Minsker's estimator.","section":"Section II.F / III / Appendix C"},{"comment":"The theoretical bounds in Theorem 1 (Eq. 13) and Theorem 2 (Eq. 23) are asymptotic, with o(1) terms that the authors explicitly ignore ('Hence, we will ignore this factor in our subsequent analysis'). The paper then compares simulated errors at N between 1000 and 50000 against these asymptotic bounds (e.g., Figures 2, 4, 5, 11). At these finite sample sizes, with k ranging from 43 to 219 and l ~ log(N/k), the o(1) terms may not be negligible, particularly because t is chosen as k/log(k) or n/l^2 log(l), so the conditions for the o(1) terms to vanish are only marginally satisfied. This weakens the claim in Section III that the practical performance 'followed the tightened bounds closely' and the associated recommendation based on Table I.","section":"Section II.B / II.C"},{"comment":"The empirical ordering within the modified family contradicts the theoretical ARE comparison. Section II.D derives a higher ARE for MomCyc than MomRand (Eqs. 29 and 32), but Section III states: 'Despite the higher ARE of MomCyc compared to MomRand, the latter showed better performance for Clifford measurements.' This inconsistency indicates that the asymptotic relative efficiency does not predict the finite-sample behavior, so attributing the Mom-versus-MomRand gap to Minsker's estimator per se, rather than to the specific values of k, l, and m, is unsupported without a matched-hyperparameter comparison.","section":"Section II.D / Section III"}],"minor_comments":[{"comment":"The sentence 'This shows that Minsker's estimator offers and advantage over the traditional MoM protocol for Clifford measurements' contains a typo: 'and advantage' should be 'an advantage'.","section":"Section III"},{"comment":"In Algorithm 4, the loop 'for i ← 0, m do' should likely be 'for i ← 0, m−1 do' for consistency with the other algorithms and to generate exactly m rounds.","section":"Algorithm 4"},{"comment":"The text 'Therefore, t = log(2M/δ). To satisfy the condition t ≪ k, we will choose t = k/log(k)' is confusing: k is a free parameter, and setting t = k/log(k) changes the failure probability from the union-bound value. Please clarify how k is chosen so that k/log(k) is consistent with log(2M/δ) for the reported M and δ.","section":"Section II.B"},{"comment":"Table I gives the number of samples required for 'an average error of ε = 0.1' but the caption does not state the values of M, δ, and the estimator parameters used. Please include these in the caption for reproducibility.","section":"Table I"},{"comment":"Figure 13 is only referenced in Appendix C; it would be helpful to refer to it also in the main text when discussing the k-dependence of the Pauli results, since it is central to the interpretation of the Clifford results.","section":"Appendix C / Figure 13"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the journal's scope and the numerical experiments are clearly described. The main obstacle is the missing matched-k control for the Clifford claim. A revision that adds a Clifford k-sweep (varying the number of groups or group size for both Mom and the modified estimators) and addresses the finite-sample validity of the asymptotic o(1) bounds would be sufficient to make the central claim convincing. I would not recommend rejection, as the issue appears fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid benchmarking paper that imports Minsker's sharpened MoM estimator into classical shadows via two incomplete U-statistic designs (random and cyclic), and compares them against the usual MoM and the plain mean for Pauli and Clifford measurements. The authors report the results straight: the simple mean wins every simulation, and the modified estimators fail on Pauli measurements and on the quadratic purity task. They even include appendices checking Gaussianity and analyzing the Pauli k-dependence. That is honest practice and earns credit.\n\nWhat is genuinely new is the application itself and the two concrete sampling schemes, MomRand and MomCyc. The theory is not theirs, and they cite Minsker and Lee properly. The central claim, that MomRand/MomCyc beat Mom for Clifford fidelity estimation, is where the soft spot sits. The stress-test note is correct: Mom runs at k=43 while the modified estimators run at k between 65 and 219, so the gap could be a hyperparameter artifact. The paper itself shows for Pauli measurements that error depends most heavily on k, not estimator type, and no analogous k-sweep is provided for Clifford. That is not a minor omission; it is the load-bearing missing control. The theory also does not predict the within-family ordering: MomCyc has higher ARE than MomRand yet performs worse empirically, so attributing the Cliffard gap to \"Minsker's estimator\" is unsupported without a matched-k, matched-m experiment.\n\nMinor weaknesses: the o(1) terms in the asymptotic bounds are dropped at sample sizes where they may not be negligible, and no code is released, making the exact parameter choices hard to reproduce. Table I compares bounds rather than achieved estimator performance, and it is the mean that actually needed the fewest shots in the simulations.\n\nProportionately: the paper is not a mess. The numerics are direct simulation, not curve fitting; the external theorems are correctly cited; the negative results are reported without spin; and the system-size independence check is a nice addition. The qualitative finding that estimator choice interacts with the unitary ensemble is plausible and useful. The specific quantitative advantage for Clifford measurements needs a k-controlled experiment and ideally code before it becomes a recommendation.\n\nFor whom: practitioners choosing post-processing estimators for shadow data, and people working on finite-sample MoM constants. I would send it to peer review, asking for a matched-k Clifford sweep and a discussion of why MomCyc underperforms its ARE. The paper deserves referee time, but the headline claim needs to be firmed up first.","headline":"A useful, honest benchmark of Minsker's median-of-means estimator for classical shadows, but the headline Clifford advantage is confounded by unmatched k values and needs a controlled comparison before it carries weight.","tokens_in":26365,"tokens_out":1745,"would_cite":false,"duration_ms":18353,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"The paper claims that swapping in a modified median-of-means estimator lowers classical-shadow error for global Clifford measurements.","keywords":["classical shadows","median-of-means estimator","U-statistics","incomplete U-statistics","Clifford measurements","Pauli measurements","GHZ state","shot complexity"],"falsifier":"Run the GHZ fidelity benchmark with all estimators forced to use the same number of groups $k$ at each shadow size; if the modified estimators no longer beat the original, the claimed advantage is a $k$ artifact.","tokens_in":25324,"feed_emoji":"⚛️","tokens_out":8522,"duration_ms":81153,"temperature":0.7,"pith_summary":"This paper tries to establish that the practical shot count of the classical shadows protocol can be reduced by replacing its standard median-of-means estimator with a modified estimator carrying tighter concentration constants. It supplies two efficient implementations of the modified estimator based on incomplete U-statistics, one using random sampling of subset averages and one using cyclically permuted sampling, and benchmarks them against the original estimator numerically. The central reported result is a setting-dependent ranking: for Pauli measurements on a 50-qubit Ising chain the original estimator remains the best, but for global Clifford measurements used to estimate the fidelity of noisy GHZ states the modified estimators achieve lower error and variance at the same shadow sizes. If that comparison holds, switching estimators in the classical post-processing step would lower measurement overhead for Clifford-based shadow estimation without changing the experiment.","feed_headline":"Modified median-of-means estimator cuts Clifford shadow error","feed_subtitle":"A purely classical post-processing swap lowers error and variance at equal shadow sizes, and may cut required shots.","key_machinery":"The argument runs on the modified median-of-means estimator, which splits the shadow data into groups, forms averages, then takes the median of averages over all (or a sampled subset of) $l$-element combinations of the group means, a U-statistic step. This changes the constant in the tail bound from $8e^2$ or $\\sqrt{\\pi}+o(1)$ for the standard estimator to $\\sqrt{2}+o(1)$, which is what lowers the predicted shot count. Because taking all combinations is computationally expensive, the paper implements two incomplete U-statistic designs: a random sampling design and a cyclic-permutation design whose offsets form a Golomb ruler, and it uses variance formulas for incomplete U-statistics to compare them.","core_discovery":"With global Clifford measurements, the modified median-of-means estimators outperform the standard median-of-means estimator: in simulations estimating the fidelity of noisy GHZ states, the modified estimators had lower average error and variance than the original estimator at equal shadow sizes, and their 3.3-sigma errors stayed under the new tail bound while the original estimator's exceeded it. The paper interprets this as evidence that the tighter constants in the modified estimator produce a real practical advantage for Clifford measurements. With Pauli measurements the order reverses: the original estimator performs best, and the paper's appendix attributes the difference mainly to the number of groups $k$ rather than to the estimator type, because each group has fewer hits on a given Pauli observable.","pith_inferences":["Because the appendix shows that the Pauli-measurement ranking is governed by the number of groups $k$, the Clifford advantage may also depend on $k$; a fair test would run all estimators with the same $k$, and until that is done the advantage should be treated as provisional.","If a same-$k$ test confirms the advantage, the practical rule would be estimator selection by measurement ensemble: standard median-of-means for Pauli observables, modified estimators for global Clifford observables.","The theory predicts the cyclic design has higher asymptotic relative efficiency than random sampling, yet the paper observes the random version performing at least as well in the Clifford benchmark; understanding this gap could reveal finite-sample effects that a follow-up could test."],"forward_implications":["If the comparison holds, global-Clifford shadow estimation can use fewer shots for the same target fidelity by switching the post-processing estimator to one of the modified versions.","The improvement is purely classical, so existing classical-shadow datasets collected with Clifford measurements could be reanalyzed without new quantum experiments.","For Pauli measurements, the modified estimators are not a safe swap: the original estimator had the lowest error, and the group-size effect in the appendix warns against using them there.","The new tail bound is reported to be tight for Clifford measurements, which means the theoretical shot-count reduction is not just an artifact of a loose bound."],"supporting_citations":[{"why":"Defines the classical shadows protocol and the original median-of-means estimator whose loose constants motivate this work.","marker":"[1]"},{"why":"Provides the modified median-of-means estimator with the tighter constant that the paper implements and benchmarks.","marker":"[82]"},{"why":"Supplies the sharp median-of-means tail bound with the $\\sqrt{\\pi}+o(1)$ constant used as the improved original bound.","marker":"[83]"},{"why":"Gives the incomplete U-statistics theory and variance formulas behind the random and cyclic sampling designs.","marker":"[84]"},{"why":"Establishes the exponential hit-count dependence for Pauli observables that the paper's appendix uses to explain the $k$-dependence of the estimators.","marker":"[89]"}],"fun_headline_variants":["Tighter MoM cuts error for Clifford shadow estimation","Clifford shadows improve with modified median-of-means","Shadow estimator trade-off: Clifford gains, Pauli loses","U-statistic MoM betters Clifford shadows at same cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison assumes the observed Clifford-measurement advantage comes from the estimator type and not from the different number of groups $k$ each estimator was run with, since the appendix itself shows $k$, not estimator type, drives the Pauli-measurement results.","fun_headline_variants_meta":{"raw":{"variants":["Tighter MoM cuts error for Clifford shadow estimation","Clifford shadows improve with modified median-of-means","Shadow estimator trade-off: Clifford gains, Pauli loses","U-statistic MoM betters Clifford shadows at same cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1503,"prompt_tokens":955,"completion_tokens":548,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":481}},"tokens_in":571,"tokens_out":548,"duration_ms":5486,"temperature":1.0,"reasoning_tokens":481,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:26:54.124072+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the GHZ fidelity benchmark with all estimators forced to use the same number of groups $k$ at each shadow size; if the modified estimators no longer beat the original, the claimed advantage is a $k$ artifact.","supporting_citations":[{"cited_title":"Minsker, Efficient median of means estimator, in Pro- ceedings of Thirty Sixth Conference on Learning The- ory, Proceedings of Machine Learning Research, Vol","cited_arxiv_id":null,"evidence_quote":"Provides the modified median-of-means estimator with the tighter constant that the paper implements and benchmarks."},{"cited_title":"Minsker, U-statistics of growing order and sub-Gaussian mean estimators with sharp constants, Mathematical Statistics and Learning 7, 1 (2023)","cited_arxiv_id":null,"evidence_quote":"Supplies the sharp median-of-means tail bound with the $\\sqrt{\\pi}+o(1)$ constant used as the improved original bound."}],"review_version":1}