{"id":"fb2469e6-275d-4b7f-b8df-6bf6cd0487d4","arxiv_id":"1908.08909","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Random Clifford measurements produce a classical shadow of a quantum state that predicts M linear features using only O(log M) measurements, independent of system size, with a matching lower bound.","lead":"This paper introduces a classical shadow representation of a quantum state, built from random Clifford measurements, that permits predicting many properties from remarkably few measurements. The approach is sample-optimal within its measurement class and is demonstrated on systems up to 162 qubits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the core sample-complexity claim is sound; only informal overstatements in the lower-bound discussion do not undermine correctness.","rationale":"The reader's weakest assumption was that stabilizer states form a complex projective 3-design, which is a proven theorem and is indeed the load-bearing mathematical premise. My independent pass through the main proof of Theorem 4 confirms the argument: the variance bound follows from the 2-design part of this assumption, the median-of-means analysis is standard, and the union bound over M is valid. The lower-bound proof has some technical rough edges — notably a case-1 condition mismatch and a non-strict union bound — but the authors explicitly state that cases 2 and 3 alone prove Theorem 6, and those cases do cover all parameter regimes. The informal statement of Theorem 2 is stronger than the formal min(...) result, but the formal result is correct and the paper's abstract and summary rely on the formal claims. Given the paper's rigorous main theorems, honest disclosure of limitations, and supportive numerics, the ACCEPT verdict stands without modification.","tokens_in":20940,"tokens_out":30005,"duration_ms":283388,"concrete_test":"Independently re-derive Theorem 6 with explicit constants, focusing on cases 2 and 3: verify that the construction of the codebook and the union bound in Lemma 2 can be made strict by taking M' = exp(min(log M, rD/64)) instead of exp(min(log M, rD/32)), and confirm that this yields the same Ω(min(B logM/ε^2, B^2D/ε^4, BD^2/ε^2)) statement for all B, ε, D, M. If the min formula changes or a regime is uncovered, the optimality claim would require revision; otherwise the formal lower bound is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central claim. Theorem 4 is correctly derived: the stabilizer-state 3-design (Eqs. A2-A3) gives the variance bound Var <= 3 tr(O^2), and median-of-means concentration with a union bound over M yields N = O(log(M/δ) max_i tr(O_i^2)/ε^2). The proof details check out, including the unbiasedness of the single-copy estimator and the robustness of the median to heavy-tailed contributions. The lower-bound Theorem 6 is more delicate. Its formal statement is the min(B log(M)/ε^2, B^2D/ε^4, BD^2/ε^2), and the authors correctly note that cases 2 and 3 alone prove the theorem. Case 1 contains a technical gap: it chooses rank-B/4 projectors but Lemma 2 requires M <= exp(rD/32) = exp(BD/128), which can fail when B < 4 even if M <= exp(D/32). However, cases 2 and 3 cover all parameter regimes, so this gap does not threaten the formal theorem. The informal Theorem 2 ('requires at least log(M) max_i tr(O_i^2)/ε^2') is an overstatement: the proven lower bound is the minimum of three terms, and for M super-exponential in D the first term is not the operative bound. This is a presentation-level imprecision, not a flaw in the mathematical argument. The paper's own discussion of the HS-norm limitation is honest, and the numerical experiments are supportive. No correctness issue rises to the level of changing the verdict.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces and analyzes a 'classical shadow' protocol for predicting linear features tr(O_i rho) of an unknown n-qubit state rho from independent random Clifford measurements. The protocol stores the classical descriptions of the resulting stabilizer states and uses median-of-means estimation to predict M features. The main formal result (Theorem 4, Appendix A) states that N = O(log(M/delta) max_i tr(O_i^2)/eps^2) single-copy measurements suffice to predict all M features to accuracy eps with failure probability at most delta, a bound independent of the Hilbert space dimension D = 2^n. Theorem 5 gives improved bounds for very large M, and Theorem 6 (Appendix B) provides a matching information-theoretic lower bound for any prediction procedure based on a fixed set of independent measurements, up to logarithmic factors. The paper also reports numerical experiments for GHZ states, toric-code ground states, and tripartite entanglement witnesses, comparing favorably with neural-network quantum state tomography.","tokens_in":21247,"tokens_out":5805,"duration_ms":60427,"significance":"If the central claim holds, the paper establishes an exponential compression in both the system dimension and the number of target functions for observables with bounded Hilbert-Schmidt norm, while using only tractable Clifford measurements. The main proof is complete and verifiable: Lemma 1 derives unbiasedness and the variance bound Var <= 3 tr(O^2) from the stabilizer-state 3-design property, and the median-of-means argument with a union bound yields the advertised scaling. The lower bound in Appendix B is a careful adaptation of the Flammia et al. communication argument to feature prediction, and it is not circular: it does not rely on the upper-bound construction. The paper is also commendably honest about limitations, explicitly discussing the unfavorable scaling for observables such as Pauli strings and the distinction between classical and quantum fidelity in the numerical comparisons. The numerical experiments extend to 162 qubits and support the theoretical claims in the tested regimes.","major_comments":[],"minor_comments":[{"comment":"The informal statement that any prediction procedure based on a fixed set of independent measurements 'requires at least log(M) max_i tr(O_i^2)/eps^2 state copies' overstates the formal Theorem 6, whose proven bound is the minimum of three terms. The B log(M)/eps^2 term is not the operative bound when M is super-exponential in D, so the informal statement should be qualified to match Theorem 6.","section":"Section I.E, Theorem 2 (informal)"},{"comment":"The case-1 construction assumes M <= exp(D/32), but Lemma 2 requires M <= exp(rD/32) = exp(BD/128); for B < 4 these assumptions differ. Since cases 2 and 3 alone cover all parameter regimes, this gap does not affect the formal theorem, but the exposition should either impose the stronger condition or explicitly note that the gap is covered by cases 2 and 3.","section":"Appendix B, case 1 (around Eq. (B1) and Lemma 2)"},{"comment":"There is a typo in the error-bound chain: '|ˆo = tr(Oρ)|' should read '|\\hat o - tr(Oρ)|'.","section":"Theorem 5 proof, Appendix A"},{"comment":"The phrase 'order of log(M) measurements' could be misread as a statement about distinct measurement settings; it refers to the number of single-copy measurements, i.e., state copies, and should be made explicit.","section":"Abstract and Introduction"},{"comment":"The formal lower-bound statement says the machine predicts 'with high probability' without specifying the failure probability or explicitly stating that the epsilon guarantee is uniform over the M features and all states. The proof assumes such a uniform guarantee; the statement should be aligned with the proof.","section":"Theorem 6, Appendix B"}],"recommendation":"minor_revision","confidential_remarks":"No significant concerns. The central mathematical claim is sound as far as I can verify, and the remaining issues are presentation-level. The paper is a good fit for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the paper that introduces classical shadows, and the central claim holds up: from O(log(M) max_i tr(O_i^2)/eps^2) random Clifford measurements you can predict M linear features of an unknown n-qubit state, with no dependence on dimension D = 2^n, and no agnostic measurement scheme can do better. The proof is standard and correct. The stabilizer-state 3-design gives the variance bound, median-of-means plus a union bound gives the log(M) scaling, and the lower bound adapts Flammia's communication argument to fixed independent measurements. The Clifford 3-design theorem used as input is a prior published result, so the self-citation is not a problem.\n\nThe genuinely new piece is the combination of randomized Clifford measurements, median-of-means, and feature prediction into one practical protocol with dimension-independent sample complexity, plus the matching lower bound. That is a real step beyond Aaronson's shadow tomography, which requires exponentially long joint circuits, and beyond Flammia's direct fidelity estimation, which handles one target at a time. The related-work discussion is accurate and the authors are honest about the Hilbert-Schmidt norm limitation.\n\nSoft spots are minor. The informal Theorem 2 in the main text says feature prediction 'requires at least log(M) max tr(O_i^2)/eps^2 state copies,' but the formal Theorem 6 proves a minimum of three terms; the first term is the operative one only for M up to exp(D/32) or so. The stress-test note found a technical gap in case 1 of the lower-bound proof, but cases 2 and 3 cover all regimes, so the formal theorem stands. The improvement in Theorem 5 is sketched via nets rather than fully detailed, which is fine for an auxiliary result but a referee may want more. The numerical comparison with neural network tomography compares quantum fidelity for classical shadows against classical fidelity for NNQST; the authors disclose this, but it does weaken the 'improvement over machine learning' framing. No code is released, so the numerics are not immediately reproducible.\n\nBottom line: this is a foundational paper for quantum state certification and should be sent to serious referees. The main theorems are correct; the informal lower-bound statement and the sketchiness of Theorem 5 are cosmetic, not load-bearing. My verdict is clear: worth engaging with, worth citing, and worth a full peer review.","headline":"The classical-shadow protocol is solid: the sample-complexity proof checks out, the lower bound is right up to a presentation-level overstatement, and the paper deserves a full referee.","tokens_in":21740,"tokens_out":2800,"would_cite":true,"duration_ms":30666,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","81P45"],"pacs":["03.67.-a","03.65.Wj"],"model":"deepseek-v4-flash","headline":"Random Clifford measurements, stored as a classical shadow, predict an exponential number of quantum features from only logarithmically many copies.","keywords":["classical shadows","shadow tomography","stabilizer states","Clifford group","median of means","fidelity estimation","entanglement witnesses","quantum state tomography"],"falsifier":"Numerically sample the single-copy estimator (2^n + 1)<s|O|s> - tr(O) over uniformly random Clifford unitaries for a fixed traceless observable with tr($O^{2}$) = 1; if the empirical variance ever exceeds 3, Lemma 1 fails and the sample-complexity bound collapses. More directly, run the median-of-means protocol for M random rank-one projectors and test whether accuracy epsilon is reached with C log(M)/$epsilon^{2}$ copies for a fixed constant C.","tokens_in":20743,"feed_emoji":"⚛️","tokens_out":4533,"duration_ms":49250,"temperature":0.7,"pith_summary":"This paper establishes that a fixed, measurement-agnostic classical sketch of an unknown quantum state can predict exponentially many linear features of that state. The sketch, called the classical shadow, is built from random Clifford rotations followed by computational-basis measurements, and its size scales as log(M) times the largest Hilbert-Schmidt norm of the target observables, divided by epsilon squared. This sample count is independent of the system dimension and matches a fundamental information-theoretic lower bound for any procedure that uses fixed independent measurements. The paper also demonstrates numerically that classical shadows accurately estimate fidelities, entanglement witnesses, and other features for systems with up to 162 qubits.","feed_headline":"Logarithmic measurements predict exponentially many quantum features","feed_subtitle":"Random Clifford measurements form a classical shadow that matches the information-theoretic lower bound.","key_machinery":"The central object is the classical shadow: a list of stabilizer states obtained from random Clifford measurements. The load-bearing identity is that qubit stabilizer states form a complex projective 3-design, which means sampling uniformly from them reproduces the first three moments of the Haar measure on pure states. This makes the mean and variance of the single-copy estimator exactly computable: for any observable O, the estimator o_hat = (2^n + 1)<s|O|s> - tr(O) has expectation tr(O rho) and variance at most 3 tr($O^{2}$). Median-of-means estimation then converts this bounded variance into a high-probability guarantee with only logarithmic dependence on the number of target functions.","core_discovery":"The central claim is that a classical shadow of size O(log(M) max_i tr($O_i^{2}$)/$epsilon^{2}$) suffices to predict M linear target functions tr(O_i rho) up to accuracy epsilon, for any n-qubit state rho. Each measurement is performed by applying a random Clifford circuit, measuring in the computational basis, and storing the resulting stabilizer state; prediction is then done by splitting the shadow into batches and taking the median of linear inversion estimates. Because the shadow size is independent of the dimension D = 2^n, the paper achieves an exponential compression in both the system size and the number of target functions for observables with bounded Hilbert-Schmidt norm. A matching lower bound shows that no prediction procedure based on fixed independent measurements can do substantially better, so the scaling is not an artifact of the method but a fundamental restriction.","pith_inferences":["The 3-design argument suggests that classical shadows can be built from any unitary 3-design, not necessarily the full Clifford group, with the constant in the sample bound depending on the design's fourth-moment properties.","The classical shadow is a convenient data format for downstream machine-learning tasks: once the shadow is stored, predicting any linear feature is just a median of linear functions of stabilizer overlaps, which could be combined with trained models.","For few-body observables, a shadow based on random single-qubit Clifford rotations may achieve logarithmic scaling in the number of target features with a smaller constant than global Clifford measurements, though this is not analyzed here.","The lower-bound proof technique, which uses a random rotation inserted between the state preparation and the measurement, likely extends to other estimation tasks where the measurement is agnostic to the target function."],"forward_implications":["Fidelity to an exponentially large set of pure target states can be estimated simultaneously from O(log(M)/epsilon^2) copies, independent of the number of qubits.","Entanglement verification can check exponentially many witnesses at once without adapting the measurement procedure to any specific witness.","The sample complexity O(log(M) max tr(O_i^2)/epsilon^2) is optimal: any prediction method that uses fixed independent measurements must use at least that many copies.","For observables with exponentially large Hilbert-Schmidt norm, such as global Pauli strings, classical shadows require exponentially many copies, though they still give a square-root improvement over direct measurement of every Pauli term.","The protocol is classically tractable because stabilizer states are stored with O(n^2) bits and overlaps between stabilizer states are computed in O(n^2) time."],"supporting_citations":[{"why":"Establish that qubit stabilizer states form a complex projective 3-design, supplying the moment formulas used to bound the estimator variance.","marker":"[39, 56, 58]"},{"why":"Defines the Clifford/stabilizer formalism that makes each random measurement classically storable in polynomial bits.","marker":"[24]"},{"why":"Introduces shadow tomography as the task and provides the previous sample-complexity baseline that this paper improves on for bounded-norm features.","marker":"[1, 3]"},{"why":"Provides the prior direct-fidelity-estimation method whose worst-case scaling is improved by the classical-shadow fidelity guarantee.","marker":"[19]"},{"why":"Supplies the median-of-means concentration inequality that turns bounded variance into the logarithmic dependence on the number of target functions.","marker":"[36, 44]"},{"why":"Provides the linear-inversion estimation perspective that the classical-shadow prediction phase adapts.","marker":"[29]"}],"fun_headline_variants":["Quantum shadows: log(M) measurements predict M features","Classical shadow: few measurements, many quantum features","Measurement count scales logarithmically for quantum features","Saturating quantum measurement lower bound with shadows"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire sample-count guarantee rests on the mathematical fact that Clifford orbits reproduce the first three moments of the uniform Haar measure on pure states, so the variance of a single shadow estimate is bounded by 3 tr($O^{2}$); if that 3-design property failed, the advertised scaling would not hold.","fun_headline_variants_meta":{"raw":{"variants":["Quantum shadows: log(M) measurements predict M features","Classical shadow: few measurements, many quantum features","Measurement count scales logarithmically for quantum features","Saturating quantum measurement lower bound with shadows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00049,"raw_usage":{"total_tokens":2342,"prompt_tokens":810,"completion_tokens":1532,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":426,"completion_tokens_details":{"reasoning_tokens":1472}},"tokens_in":426,"tokens_out":1532,"duration_ms":14972,"temperature":1.0,"reasoning_tokens":1472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:25:28.345952+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically sample the single-copy estimator (2^n + 1)<s|O|s> - tr(O) over uniformly random Clifford unitaries for a fixed traceless observable with tr($O^{2}$) = 1; if the empirical variance ever exceeds 3, Lemma 1 fails and the sample-complexity bound collapses. More directly, run the median-of-means protocol for M random rank-one projectors and test whether accuracy epsilon is reached with C log(M)/$epsilon^{2}$ copies for a fixed constant C.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Clifford/stabilizer formalism that makes each random measurement classically storable in polynomial bits."},{"cited_title":"Aaronson","cited_arxiv_id":null,"evidence_quote":"Provides the prior direct-fidelity-estimation method whose worst-case scaling is improved by the classical-shadow fidelity guarantee."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the linear-inversion estimation perspective that the classical-shadow prediction phase adapts."}],"review_version":1}