{"id":"2e2cbb82-def7-4967-bb42-3eed7c2e1ff0","arxiv_id":"2509.06218","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A full-stack resource analysis identifies when classical shadow estimation beats direct quantum measurement, with break-even points that depend on the number of observables, their form, and the quantum hardware.","lead":"This paper compares two ways to extract quantum information: classical shadows (random measurements plus classical processing) and direct quantum measurement, tracking both quantum and classical costs. It identifies when each method wins, with break-even points that depend on the number of observables and the hardware.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. 31 equates the shadow norm with the infinity norm for sparse Hermitian matrices; this is false for nonlocal k=1 matrices such as random diagonal observables, so the LHM frontier is unsupported.","rationale":"The reader's weakest assumption correctly targets the LHM shadow-norm estimation, but treats Eq. 31 as an approximation whose constants might be wrong. My concern is sharper: the asserted equality is false for the observable class the paper claims to analyze. A k=1 random diagonal matrix satisfies Statement 3's hypotheses, yet its shadow norm is ~2^n while Eq. 31/46 gives O(n log n); this is an internal mathematical failure, not a disagreement with consensus. Because the LHM measurement count T, the finite-advantage region in Fig. 2(d), and the hardware-specific crossovers in Fig. 3(b) all depend on this step, the central LHM claim is unsupported. The LCP analysis is less affected, but the paper's headline efficiency frontier includes the LHM case. The paper could be salvaged by restricting LHM observables to those with bounded Pauli weight and computing the shadow norm explicitly rather than replacing it by the infinity norm; as written, the generic sparse-matrix claim should be rejected.","tokens_in":20659,"tokens_out":12182,"duration_ms":121267,"concrete_test":"Take O = diag(d_1,...,d_{2^n}) with iid N(0,1) entries at n = 12, 14, 16. Compute the exact shadow norm under random Pauli measurements via the Pauli decomposition ||O - tr(O)/2^n I||_shadow^2 = Σ_{S≠∅} c_S^2 3^{|S|}, and compare it with the right side of Eq. 31/46. If the ratio grows as ~2^n/(n log 2) rather than staying constant, Eq. 31 is invalid and T in Eq. 5 is exponentially too small, so the LHM crossover in Fig. 2(d) cannot be trusted. A simpler instantiation of the same failure is O = X^{⊗n}: ||X^{⊗n}||_shadow^2 = 3^n while ||X^{⊗n}||_∞^2 = 1.","verdict_should_be":"REJECT","load_bearing_attack":"Statement 3(a)'s measurement count T (Eq. 5) is obtained by substituting into Eq. 31 the extreme-value estimate Eq. 46 of ||O - tr(O)/2^n I||_∞. Eq. 31 asserts ||O - tr(O)/2^n I||_shadow^2 = ||...||_∞^2 for sparse Hermitian matrices. This equality is not valid for the stated observable class. Under random Pauli measurements, an n-qubit Pauli P of weight w has ||P||_shadow^2 = 3^w while ||P||_∞^2 = 1. Sparse does not imply low Pauli weight: a diagonal matrix with iid N(0,1) diagonal entries has k=1 nonzero per row and decomposes as Σ_{S⊆[n]} c_S Z_S with E[c_S^2] = 1/2^n; hence E||O||_shadow^2 = Σ_S 3^{|S|}/2^n = 2^n, whereas ||O||_∞^2 = O(n log n). Thus Eq. 31 underestimates the shadow norm exponentially, not by a constant. The paper's justification that k << 2^n implies Pauli weight w << n is false: locality is not equivalent to computational-basis sparsity. Since Eq. 31 is the bridge that makes T depend only on (k,n), the LHM measurement count, the finite advantage window in Fig. 2(d), and the hardware crossover in Fig. 3(b) are not established. This failure is independent of the EVT approximation in Eq. 46; even an exact infinity norm would not fix it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript compares the resource cost of classical shadow tomography with that of direct quantum measurement (dubbed 'quantum footage') for two families of observables: linear combinations of Pauli operators (LCP) and large sparse Hermitian matrices (LHM). For LCP observables, it claims that classical shadows win when the number of observables M is large and the Pauli weight w is small, with a crossover near M ≈ 16 in the default settings (Statement 1, Statement 2, Figure 2c). For LHM observables, it claims the shadow method wins only in a finite window of M, k, and n (Statement 3, Statement 4, Figure 2d). The derivations combine standard shadow-norm bounds from Huang–Kueng–Preskill with extreme-value estimates for the infinity norm of sparse random matrices, and then convert measurement counts and floating-point operations into runtime comparisons across several hardware platforms.","tokens_in":20981,"tokens_out":7725,"duration_ms":75180,"significance":"If the results were correct, the paper would provide a practically useful rule of thumb for when classical shadows are preferable to direct measurement, and it would extend the comparison beyond measurement counts to classical post-processing and hardware-dependent runtimes. The explicit formulas for LCP measurement counts and the full-stack cost accounting are valuable features, and the authors are transparent about the parameters entering the comparison. However, the central LHM claim rests on an equality between the shadow norm and the infinity norm that is false for the stated observable class, and the LCP statement contains a coefficient-distribution inconsistency that undermines its claimed rigor. Because the LHM efficiency frontier and the hardware crossover in Figure 3(b) are direct consequences of the invalid equality, the main contribution is not currently supported.","major_comments":[{"comment":"Equation (31) asserts that for sparse Hermitian matrices the shadow norm equals the infinity norm after subtracting the normalized trace. This equality is false for the stated observable class. For an n-qubit Pauli operator P of weight w, ||P||_shadow^2 = 3^w while ||P||_infinity^2 = 1; sparsity in the computational basis does not imply low Pauli weight. A concrete counterexample is a diagonal matrix with iid N(0,1) diagonal entries, which has k = 1 nonzero per row but its Pauli decomposition has E[c_S^2] = 2^{-n}, giving E||O||_shadow^2 = sum_S 3^{|S|}/2^n = 2^n, whereas ||O||_infinity^2 = O(n log n). Thus Eq. (31) underestimates the shadow norm exponentially, and the claimed measurement count in Eq. (5), the finite advantage window in Figure 2(d), and the hardware crossover in Figure 3(b) are not established. The argument that k << 2^n implies w << n is incorrect: locality in the computational basis is not equivalent to low Pauli weight.","section":"Appendix B.3.1, Eq. (46)"},{"comment":"The extreme-value estimate in Eq. (46) approximates the infinity norm as the maximum of 2^n independent Gaussian row sums and uses the CLT for sums of k half-normal random variables. The row sums are not independent because the matrix is symmetric, so off-diagonal entries are shared between rows. Moreover, the normal approximation is invoked for all k, including small k where the CLT is not meaningful. Even if Eq. (31) were replaced by a valid shadow-norm bound, the functional dependence of Eq. (5) on k and n would still be heuristic rather than proven, so Statement 3(a) is not rigorous in its present form.","section":"Appendix B.3.1, Eq. (46)"},{"comment":"Statement 1 says the Pauli coefficients follow a standard normal distribution, but the proof in Appendix B.1.1 uses c_j ~ N(0, 0.5) truncated to [-1,1] and replaces the maximum shadow norm over observables by its expectation, with E[c_j^2] ≈ 0.25. This is not a worst-case bound: a fixed observable with coefficients drawn from N(0,1) has E||O||_shadow^2 = L * 3^w, not 0.25 L * 3^w. The factor 4 difference changes Eq. (2), and the failure probability in the theorem does not cover randomness in the coefficients unless that is explicitly stated. Statement 1 is therefore not 'rigorous' as claimed.","section":"Statement 1 and Appendix B.1.1"},{"comment":"The spectral-norm estimate for the direct-measurement side of the LHM comparison is also unreliable. Equation (62) asserts ||O|| ≈ 2 sqrt(2) sqrt(k) based on a random-matrix result for off-diagonal degrees d = k-1. For matrices with nonzero diagonal entries and small k, this can be badly wrong: a diagonal matrix with k = 1 has spectral norm equal to the largest absolute diagonal entry, which is Theta(sqrt(n)) for iid N(0,1) entries, whereas Eq. (62) gives a constant. Since Statement 4's measurement count Eq. (7) depends on this spectral norm, the quantum-footage side of the LHM comparison is not established for the actual matrix ensemble described in the paper.","section":"Appendix B.5, Eqs. (60)-(62)"}],"minor_comments":[{"comment":"The arXiv title is 'Classical Shadows versus Direct Quantum Measurement' but the manuscript title inside is 'Classical Shadows versus Quantum Footage'; please align the two.","section":"Title"},{"comment":"Equation (3) is numbered twice (Statement 2 and Statement 4); renumber the equations.","section":"Section 2"},{"comment":"The manuscript states that t_shadow/t_footage is 'rigorously shown' to be independent of epsilon, but the proof is not included in the appendix; please provide it or mark the claim as a conjecture.","section":"Section 2, bullet list"},{"comment":"The figure captions contain typos ('observales' for 'observables') and the base of the logarithm used in the crossover statements is not specified; for example, log(M) = 4 corresponds to M ≈ 16 only if log is base 2, but earlier formulas use log in the sense of the shadow literature, which is often natural log.","section":"Figures 2 and 3"},{"comment":"The FLOP accounting for the Kronecker product uses 6 FLOPs per complex multiplication and 4 multiplications per output element, but the associated additions are not fully itemized; please make the counting step-by-step.","section":"Appendix B.4"},{"comment":"The text repeatedly describes the statements as rigorous and supported by numerical experiments, but the appendix contains heuristic replacements of maxima by expectations and no numerical experiment section is provided; the Figures appear to plot the derived formulas rather than independent simulations.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The central LHM result is built on Eq. (31), which is demonstrably false for the stated observable class, and the LCP statement also contains a coefficient-distribution inconsistency that changes the claimed measurement count. These are load-bearing derivation errors rather than presentation issues. I recommend rejection; a future submission could be viable if it replaces the LHM shadow-norm analysis with a rigorous treatment and clarifies the probabilistic status of the LCP estimates."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The LCP part of this paper is a useful, if not deep, resource-accounting exercise; the LHM part is not sound. The central step that makes the LHM result work, Eq. 31, equates the shadow norm of a sparse Hermitian matrix with its infinity norm. That equality is false, and the LHM efficiency frontier is therefore unsupported.\n\nWhat is new is the full-stack cost model: they count classical FLOPs, use hardware-specific gate and measurement times, and produce break-even curves for when classical shadows are cheaper than direct measurement. The LCP analysis is a legitimate extension of Huang–Kueng–Preskill: for Pauli observables with L terms and weight w, the measurement count is the standard 34 / eps^2 * ||O||_shadow^2 * log(2M/delta), and their FLOP count for shadow post-processing (matching measurement bases rather than matrix multiplication) is a concrete, transparent estimate. The LCP crossover at M ~ 16 is the crossing of two known bounds under their parameter choices, but it is packaged in a way practitioners can use. The LHM direct-measurement estimate using sparse random matrix spectral norm ~ 2 sqrt(2k) is a reasonable heuristic.\n\nThe soft spot is not minor. Eq. 31 fails badly. Take a random diagonal matrix with independent N(0,1) diagonal entries: it has sparsity k=1 per row, but its Pauli decomposition has full support with coefficients of typical magnitude 2^{-n/2}; the shadow norm squared is ~ sum_S 3^{|S|} / 2^n = 2^n, while the infinity norm is O(sqrt(n)). So the equality underestimates the shadow norm exponentially. The paper's claim that small computational-basis sparsity implies small Pauli weight is simply wrong: a diagonal matrix is as Pauli-global as it gets. Consequently, Statement 3(a)'s T, and with it the LHM curves and hardware crossovers, are not established. The extreme-value estimate in Eq. 46 is a secondary issue; even an exact infinity norm would not fix the problem.\n\nThere is also a minor inconsistency in the LCP proof: the statement sets coefficients ~ N(0,1), while the proof uses N(0,0.5) truncated to [-1,1] (with average square 0.25), which changes the constant.\n\nWho should read this? Practitioners choosing measurement strategies might find the LCP cost model useful. The LHM claims should not be used. The paper deserves a serious referee — the LCP part is a service to the community and reviewing it can catch exactly this kind of load-bearing error — but the authors should either prove a valid shadow-norm bound for sparse matrices or retract the LHM section.","headline":"The LCP resource accounting is practical, but the LHM frontier rests on a false shadow-norm/infinity-norm equivalence that invalidates the paper's headline claim for sparse matrices.","tokens_in":21517,"tokens_out":7774,"would_cite":false,"duration_ms":67863,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","81P15"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"Classical shadows overtake direct measurement at ~16 observables","keywords":["classical shadows","direct quantum measurement","resource estimation","efficiency frontier","Pauli observables","sparse Hermitian matrices","quantum tomography","break-even analysis"],"falsifier":"Compute the exact shadow norm (Eq. 30) for randomly generated sparse Hermitian observables at, say, $n=12\\text{–}20$ qubits and sparsities $k=3\\text{–}10$, and measure how many shadow measurements are actually needed to reach $\\epsilon=0.01$ with $\\delta=0.01$; if this measured count departs systematically from Eq. (5)/(48), the crossover boundaries in Figure 2(d) move, and the finite-window advantage claim fails wherever the gap is large.","tokens_in":20414,"feed_emoji":"⚛️","tokens_out":10848,"duration_ms":83806,"temperature":0.7,"pith_summary":"This paper tries to establish a quantitative efficiency frontier between two ways of learning expectation values from an unknown quantum state: the classical shadow method, which randomizes measurements and post-processes them classically, and direct quantum measurement (“quantum footage”), which measures each observable independently. It derives closed-form resource counts for both schemes—quantum gates, number of measurement shots, and classical floating-point operations—and multiplies those counts by realistic per-operation times from four quantum hardware platforms and a supercomputer. The central result is that the shadow method is not universally efficient: for observables built as linear combinations of Pauli terms it wins only when the number of observables is large (the crossover sits near $M \\approx 16$ in the default hardware setting), and for large sparse Hermitian observables it wins only inside a finite window of the number of observables, sparsity, and qubit count. This matters because it converts a folklore “shadows are good” into a concrete, parameter-dependent recommendation for when to use which method.","feed_headline":"At ~16 observables, classical shadows overtake direct measurement","feed_subtitle":"Pauli and sparse-matrix observables have different, hardware-dependent break-even points.","key_machinery":"The central objects are the resource-count formulas themselves: the shadow measurement bound $T \\lesssim (34/\\epsilon^2)\\max_i \\|O_i\\|^2_{\\mathrm{shadow}}\\log(2M/\\delta)$ and the Hoeffding-based bound $T' \\lesssim (b-a)^2/(2\\epsilon^2)\\log(2/\\delta')$ for direct measurement, converted into runtime by per-gate and per-measurement latencies. For the sparse-Hermitian case the load-bearing step is replacing the shadow norm of $O-\\mathrm{tr}(O)2^{-n}I$ with its infinity norm (Eq. 31), then estimating that infinity norm as $k\\sqrt{2/\\pi}+\\sqrt{k(1-2/\\pi)2n\\log 2}$ via extreme-value theory over the $2^n$ row sums (Eq. 46). That estimate is what turns the abstract shadow norm into a closed expression in the sparsity $k$ and qubit number $n$.","core_discovery":"On its own terms, the paper claims that the total runtime of the two methods can be compared through the upper-bound formulas in Statements 1–4: for linear-combination-of-Pauli observables, the shadow method needs $T \\lesssim 17L\\,3^w\\,\\epsilon^{-2}\\log(2M/\\delta)$ measurements and $ML(T(1/3)^w(w+1)+2\\log(2M/\\delta)+2)$ floating-point operations, while direct measurement needs $T' \\lesssim 0.5ML^3\\epsilon^{-2}\\log(2ML/\\delta)$ measurements; for sparse Hermitian observables, the shadow count is governed by an estimated infinity norm of the observable and the direct count by its spectral norm. Evaluating these formulas with hardware gate/measurement times and supercomputer FLOP rates produces the crossover: for Pauli-type observables the shadow method becomes cheaper around $\\log M = 4$, and for sparse matrices there is a finite advantage window in $M$ that eventually closes because classical processing grows exponentially in the qubit number. The runtime ratio of the two schemes is shown to be independent of the precision $\\epsilon$.","pith_inferences":["One testable extension is an adaptive strategy that switches between direct measurement and shadows at the predicted crossover points; such a hybrid should dominate either fixed choice, but the paper does not implement it.","The infinity-norm shortcut used for sparse matrices is specific to Pauli measurements; for Clifford shadows the same shortcut would likely fail because the shadow norm is not row-local, so a different norm estimate would be needed to extend the comparison.","The crossover near $M\\approx 16$ implies a simple rule of thumb—use direct measurement for fewer than about a dozen Pauli-type observables—but this threshold depends on the ratio of gate time to measurement time and should be recalculated for each new hardware generation."],"forward_implications":["For Pauli-type observables, the shadow method is the cheaper choice once the number of observables exceeds roughly 16; below that, direct measurement costs less for typical hardware.","For sparse Hermitian observables, the advantage is non-monotonic: shadows win for intermediate $M$ but lose again for very large $M$ because classical post-processing grows exponentially with the qubit number.","The break-even point depends on hardware: photonic computers push the crossover to larger $M$ or eliminate it for the sparse-matrix case, while superconducting, ion-trap, and neutral-atom devices behave similarly.","The runtime ratio $t_{\\mathrm{shadow}}/t_{\\mathrm{footage}}$ is independent of the target precision $\\epsilon$, so the frontier does not move as accuracy requirements tighten.","Because all shadow costs are upper bounds, in practice the shadow method may be even cheaper than the predicted frontier suggests."],"supporting_citations":[{"why":"Supplies the classical shadow protocol, the shadow-norm bound $3^w$ for Pauli observables, and the theoretical basis for the infinity-norm replacement in the sparse case.","marker":"[11]"},{"why":"Provides per-gate and per-measurement time scales for superconducting, ion-trap, photonic, and neutral-atom quantum computers.","marker":"[15]"},{"why":"Supplies the supercomputer FLOP/s figure used to convert classical floating-point counts into runtime.","marker":"[14]"},{"why":"Hoeffding's inequality, the probabilistic bound behind the quantum-footage measurement-count formulas in Statements 2 and 4.","marker":"[16]"},{"why":"Supplies the random-matrix-theory spectral-norm estimate used for the sparse-matrix quantum-footage count.","marker":"[19]"}],"fun_headline_variants":["Efficiency frontier: shadows beat direct quantum measurement at ~16 observables","Classical shadows win for many observables, low Pauli weight","Sparse-matrix observables: a finite window where shadows win","Runtime ratio independent of precision in shadow vs direct"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sparse-matrix branch of the paper stands or falls on the approximation that the shadow norm of a sparse random Hermitian observable equals its infinity norm and that this infinity norm is given by the extreme-value estimate $k\\sqrt{2/\\pi}+\\sqrt{k(1-2/\\pi)2n\\log 2}$; if that statistical estimate is wrong, the predicted measurement counts and the claimed advantage window shift or disappear.","fun_headline_variants_meta":{"raw":{"variants":["Efficiency frontier: shadows beat direct quantum measurement at ~16 observables","Classical shadows win for many observables, low Pauli weight","Sparse-matrix observables: a finite window where shadows win","Runtime ratio independent of precision in shadow vs direct"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000628,"raw_usage":{"total_tokens":2968,"prompt_tokens":1076,"completion_tokens":1892,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":692,"completion_tokens_details":{"reasoning_tokens":1820}},"tokens_in":692,"tokens_out":1892,"duration_ms":13098,"temperature":1.0,"reasoning_tokens":1820,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:18:04.571636+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact shadow norm (Eq. 30) for randomly generated sparse Hermitian observables at, say, $n=12\\text{–}20$ qubits and sparsities $k=3\\text{–}10$, and measure how many shadow measurements are actually needed to reach $\\epsilon=0.01$ with $\\delta=0.01$; if this measured count departs systematically from Eq. (5)/(48), the crossover boundaries in Figure 2(d) move, and the finite-window advantage claim fails wherever the gap is large.","supporting_citations":[{"cited_title":"Nature Physics16(10), 1050– 1057 (2020)","cited_arxiv_id":null,"evidence_quote":"Supplies the classical shadow protocol, the shadow-norm bound $3^w$ for Pauli observables, and the theoretical basis for the infinity-norm replacement in the sparse case."},{"cited_title":"https://www.top500.org/lists/ green500/","cited_arxiv_id":null,"evidence_quote":"Supplies the supercomputer FLOP/s figure used to convert classical floating-point counts into runtime."},{"cited_title":"The collected works of Wassily Hoeffding, 409–426 (1994)","cited_arxiv_id":null,"evidence_quote":"Hoeffding's inequality, the probabilistic bound behind the quantum-footage measurement-count formulas in Statements 2 and 4."},{"cited_title":"Data acquisition and processing are the challenges with two major effort-intensive steps of the construction process","cited_arxiv_id":null,"evidence_quote":"Supplies the random-matrix-theory spectral-norm estimate used for the sparse-matrix quantum-footage count."}],"review_version":1}