{"id":"00aad63c-ed8b-47fa-8ba7-9067bd9d3e65","arxiv_id":"2608.08429","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For shadow tomography of Pauli observables, the optimal sample complexity is often the reciprocal fractional chromatic number of the frustration graph, achievable by Clifford measurements.","lead":"This paper finds optimal measurement strategies for estimating many properties of a quantum state from limited copies, using graph theory to decide which measurements to make. It shows that simple Clifford measurements are enough in many realistic settings, and that the method improves energy estimation for small molecules.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4's two-qubit Clifford optimality hinges on an unproved companion classification; if any two-qubit Pauli frustration graph is ℏ-imperfect, the main block-local claim fails.","rationale":"The reader identified the same external dependency, and my stress-test confirms it is the load-bearing point. The proof of Theorem 3 is otherwise coherent, and the rank-over-F2 observation suggests the two-qubit classification may well be true, but the paper as submitted does not establish it. A conditional verdict is appropriate until the classification is independently verified or included in a revised version.","tokens_in":22047,"tokens_out":11854,"duration_ms":127208,"concrete_test":"Exhaustively enumerate all 2^15 − 1 nontrivial subsets of the 15 two-qubit Pauli observables; for each induced frustration graph G, test ℏ-perfectness by checking whether BETA(G) = STAB(G), e.g., by solving the SPO hierarchy of SM Eq. (11) at r = 2 (or using the companion code at https://github.com/wangjie212/BetaNumber) to search for a weight vector w with β(G,w) > α(G,w). If every graph passes, the companion classification is confirmed for the two-qubit case and Corollary 4 stands; a single failure refutes it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is the invocation of [25] in Corollary 4: \"the graph of any Pauli observables on two qubits is always ℏ-perfect [25].\" This is what turns the general interval δτ ∈ [1/χf(G(τ)), 1/ϑ(G̅(τ))] of Theorem 3 into the equality δτ = 1/χf(G(τ)) with local Clifford optimality in the two-qubit block scenario. The present text contains no proof of this classification, and [25] is a companion preprint by the same group rather than a published or included derivation. The concern is not merely aesthetic: ℏ-imperfect realizations exist (e.g., anti-C7, which is excluded from two qubits only by a rank-over-F2 argument that is not given), so the two-qubit claim is a nontrivial structural fact. If any induced subgraph of the 15-vertex two-qubit Pauli anticommutation graph failed ℏ-perfectness, the lower bound in Theorem 3 would not be tight, the Clifford construction in SM D would not be optimal, and Corollary 4 would be false. A secondary but minor issue is the unreconciled de Finetti constant (main text 4(2d_i − max_i d_i)/(m+2) vs SM 8d_i/(m+2)); it does not affect the main claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies memoryless shadow tomography of Pauli observables under block-local measurement constraints, where each copy is measured once and entangling measurements are limited to blocks of at most m qubits. The authors introduce a partition-dependent sample-complexity parameter δτ, prove a min-max reformulation over product states (Lemma 2), and show that δτ lies between the reciprocal fractional chromatic number and the reciprocal Lovász number of a certain union of local frustration graphs (Theorem 3). They further prove that Clifford measurements attain the lower bound whenever the local frustration graphs are ℏ-perfect or the union graph is perfect, and they specialize this to two-qubit blocks (Corollary 4). The paper also presents SDP hierarchies, a see-saw/multiplicative-weights algorithm for general graphs, and applies the framework to molecular Hamiltonian estimation with reported variance improvements over existing joint-measurement strategies.","tokens_in":22279,"tokens_out":14275,"duration_ms":143039,"significance":"If the results hold, this is a substantial contribution to shadow tomography with realistic measurement constraints. The graph-theoretic reduction is clean, the derivations are parameter-free, and the paper provides concrete algorithmic constructions together with molecular benchmarks that are derived rather than fitted. The inclusion of reproducible code and the convergence analysis of the numerical hierarchies are notable strengths. The main caveat is that one headline claim — two-qubit Clifford optimality — depends on a classification imported from a companion preprint, and one step of the main theorem's proof is stated without the supporting argument for the unconditional lower bound. These issues are local and fixable, but they need to be addressed before the claims can be taken as fully established.","major_comments":[{"comment":"Corollary 4 asserts that for any partition into pairs of qubits, δτ = 1/χf(G(τ)) with local Clifford optimality, citing [25] for the statement that every Pauli frustration graph on two qubits is ℏ-perfect. This classification is not proved in the present manuscript or its Supplemental Material, and [25] is a companion preprint by the same group rather than an included derivation. Because Corollary 4 is the basis for the abstract's claim of optimality in 'all two-qubit measurement scenarios' and for the two-qubit columns in Tables I and II, this dependency is load-bearing. The authors should either supply a proof of the two-qubit classification (the case is finite and likely amenable to a rank-over-F2 case analysis) or explicitly state Corollary 4 and the associated numerical results as conditional on the companion work.","section":"Corollary 4"},{"comment":"Theorem 3 states the interval δτ ∈ [1/χf(G(τ)), 1/ϑ(G(τ))] unconditionally, but the proof in the Supplemental Material only establishes the lower bound under the additional assumption that all Gj are ℏ-perfect (leading to δτ = 1/χf(G(τ))) or that G(τ) is perfect. The main text asserts that for ℏ-imperfect Gj, '1/χf(G′) might only provide a lower bound', but no proof of this unconditional lower bound is given. Please add the missing argument (for example, using common eigenstates for each independent set of G(τ) to lower-bound the min-max expression) or restate the theorem with the hypotheses under which each bound is proved.","section":"SM Sec. C, proof of Theorem 3"}],"minor_comments":[{"comment":"The quantum de Finetti convergence bound is stated with different constants in the main text (4(2d_i − max_i d_i)/(m+2)) and in the Supplemental Material (8d_i/(m+2), Eqs. (24)–(25)). These should be reconciled, and the derivation should be checked against the cited theorem.","section":"Main text, 'Optimal measurement strategies' / SM Sec. A B"},{"comment":"The discussion of the bipartition case first defines the frustration graph of {Si} as the XOR union of G1 and G2, then switches to the edge-union G′ for the fractional-chromatic-number bound. This transition is confusing and should be clarified explicitly, since G′ rather than the XOR graph is the graph appearing in Theorem 3.","section":"Main text, bipartition discussion"},{"comment":"There is a typo in the final paragraph: 'acounts for' should be 'accounts for'.","section":"Conclusion"},{"comment":"Reference [25] is a preprint; since Corollary 4 relies on it, the authors should state its status and provide a version identifier, or avoid the dependence by proving the needed two-qubit classification in this work.","section":"Reference [25]"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are generally sound and the numerical methods are valuable, but the paper's headline claim about two-qubit Clifford optimality rests on an unpublished companion classification. This is a scope and provenance concern: the journal should insist that the needed result be proved in the manuscript or that the claim be made explicitly conditional. The missing unconditional lower-bound proof in Theorem 3 is easily fixable but should not remain as an unstated gap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new piece is the block-local setting: for a fixed partition τ, the sample complexity parameter δτ is sandwiched between 1/χf(G(τ)) and 1/ϑ(Ḡ(τ)), with equality and Clifford optimality when the local frustration graphs are ℏ-perfect or G(τ) is perfect. The two-qubit result (Corollary 4) is new relative to the cited literature and, if correct, gives a clean answer for the practically relevant case of two-qubit joint measurements. The molecular variance bounds are derived, not fitted, and they improve on McNulty et al. over the tested molecules. The SM has real proofs, not just sketches.\n\nThe main soft spot is exactly where the stress-test points: Corollary 4 leans entirely on the assertion that every two-qubit Pauli frustration graph is ℏ-perfect, citing the companion preprint [25]. The present text gives no proof, and the exclusion of a rank-over-F2 obstruction like anti-C7 is not shown here. If [25] fails, the equality δτ = 1/χf and the local Clifford optimality fail with it. The general interval in Theorem 3 is safe, so the paper does not collapse; but a standalone reader cannot verify the flagship corollary from the text alone. For a journal submission, I would want either a proof of the two-qubit classification in the SM or a very clear statement that the result depends on a companion paper that is available and under review.\n\nTwo minor issues: the de Finetti constant differs between the main text (4(2d_i − max_i d_i)/(m+2)) and the SM (8d_i/(m+2)); it is cosmetic and does not affect the main theorems, but it should be fixed. The table reproducibility would be easier with pinned code/data versions; the GitHub link is good, but not versioned for the main tables.\n\nOn the citation pattern: the paper imports beta-number bounds, ℏ-perfectness, and Clifford optimality from the authors' own prior works. That is not circular as long as those results are proven, and they are. The benchmarks are honest; the comparison to [27] is apples-to-apples enough.\n\nWho gets value: anyone working on classical shadows, Pauli estimation, or energy estimation on near-term hardware. It deserves a serious referee; the dependency on [25] should be flagged to the referee, but the core framework is solid. I would send it out rather than desk reject.","headline":"Solid extension of the beta-number framework to block-local shadow tomography; the two-qubit Clifford optimality rests on a companion-paper classification that should be visible to referees.","tokens_in":22850,"tokens_out":2499,"would_cite":true,"duration_ms":25223,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","05C15","05C69","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shadow-tomographing Pauli observables optimally reduces to a single graph number, and Clifford measurements achieve it for all one- and two-qubit blocks.","keywords":["shadow tomography","Pauli observables","frustration graph","sample complexity","Clifford measurements","hbar-perfect graphs","fractional chromatic number","Hamiltonian energy estimation"],"falsifier":"Enumerate all two-qubit Pauli realizations, compute for each resulting frustration graph the weighted $\\beta$ number via SDP and compare with the weighted independence number; finding any two-qubit graph with $\\beta(G,w)>\\alpha(G,w)$ for some weight vector $w$ would make the claimed Clifford optimality for two-qubit partitions false. Alternatively, on a concrete two-qubit partition compute $\\delta_\\tau$ by the SDP hierarchy and compare with $1/\\chi_f(G(\\tau))$; a gap would refute Corollary 4.","tokens_in":21839,"feed_emoji":"⚛️","tokens_out":8948,"duration_ms":87280,"temperature":0.7,"pith_summary":"Shadow tomography promises to estimate many expectation values of an unknown quantum state from few copies, but existing guarantees rarely come with strategies that can be implemented on real devices. This paper shows that, for Pauli observables measured one copy at a time with measurements restricted to fixed blocks of qubits, the optimal sample-complexity parameter is controlled by a single graph built from Pauli anticommutation relations. The central result pins this parameter between the reciprocal fractional chromatic number and the reciprocal Lovász number of the union frustration graph; when the local graphs are $\\hbar$-perfect, or the union graph is perfect, the lower bound is exact and Clifford measurements achieve it. This makes optimal shadow tomography constructive for all one-qubit and two-qubit measurement blocks, and it yields concrete variance bounds for molecular Hamiltonian energy estimation.","feed_headline":"Shadow tomography: Clifford measurements are optimal on two qubits","feed_subtitle":"For one- and two-qubit blocks, the optimal sample cost is set by a single graph number, and Clifford measurements achieve it.","key_machinery":"The load-bearing object is the frustration graph of a set of Pauli observables: vertices are observables, edges join anticommuting pairs; for a block partition the paper forms the edge-union $G(\\tau)$ of the frustration graphs of the local restrictions. The key identity is $\\delta_\\tau(\\{S_i\\}) = \\min_{w\\in\\Delta}\\max_{\\rho\\in \\mathrm{PD}_\\tau} \\sum_i w_i \\langle S_i\\rangle_\\rho^2$, which reduces sample complexity to an optimization over product states. The comparison theorem then sandwiches this quantity between $1/\\chi_f(G(\\tau))$ and $1/\\vartheta(\\overline{G(\\tau)})$. The class of $\\hbar$-perfect graphs—graphs for which the weighted $\\beta$ number $\\beta(G,w)=\\max_\\rho\\sum_iw_i\\langle S_i\\rangle_\\rho^2$ equals the weighted independence number $\\alpha(G,w)$ for all $w$—is exactly what makes the lower bound exact, because on such graphs Clifford measurements attain the fractional chromatic number.","core_discovery":"For a set of Pauli observables and a partition $\\tau$ of the qubits into independently measured blocks, the paper defines an optimal sample-complexity parameter $\\delta_\\tau(\\{S_i\\})$ and proves $\\delta_\\tau(\\{S_i\\})\\in[1/\\chi_f(G(\\tau)),1/\\vartheta(\\overline{G(\\tau)})]$, where $G(\\tau)$ is the edge-union of the local frustration graphs of the observables' restrictions to each block. The lower bound is tight—and achievable by randomizing Clifford measurements—whenever each local frustration graph is $\\hbar$-perfect, meaning its $\\beta$ number coincides with its weighted independence number for every weight vector, or when $G(\\tau)$ is a perfect graph. Consequently, for any partition into pairs of qubits the optimal parameter equals $1/\\chi_f(G(\\tau))$ and local Clifford measurements are sufficient. For general graphs the paper supplies SDP hierarchies and a multiplicative-weight scheme that approximate $\\delta_\\tau$ from above and below and construct near-optimal ensembles, with numerical evidence that the gap closes quickly on small graphs. Applied to Hamiltonian estimation, the resulting strategies give variance bounds that improve on optimized joint-measurement baselines for small molecules.","pith_inferences":["If the $\\hbar$-perfect classification were extended from one- and two-qubit Pauli realizations to three-qubit blocks, the same proof would immediately make Clifford measurements optimal for those partitions as well.","The sandwich bounds suggest a practical workflow for fixed-connectivity hardware: compile the Hamiltonian under the device's partition, compute $\\chi_f(G(\\tau))$ and $\\vartheta(\\overline{G(\\tau)})$ once, and use the gap as a certificate of how much is lost by the hardware constraint.","One open question implied by the paper is whether the lower bound $\\max_{\\tau}1/\\chi_f(G(\\tau))$ for unrestricted partition choice is ever tight; that could be probed numerically with the hierarchy on small systems."],"forward_implications":["Under any partition into two-qubit blocks, the optimal sample-complexity parameter is exactly the reciprocal fractional chromatic number of the union frustration graph, and local Clifford measurements achieve it.","When only single-qubit measurements are allowed, Clifford measurements reduce to Pauli measurements, so Pauli measurements are optimal in that scenario.","For any partition whose local frustration graphs are all $\\hbar$-perfect, or whose union graph is perfect, the same exactness holds: Clifford measurements are optimal and no better strategy exists.","For general frustration graphs, the SDP hierarchy and multiplicative-weight method produce near-optimal measurement ensembles; on all graphs with at most seven vertices the first hierarchy level already gives the exact sample-complexity parameter.","For molecular Hamiltonian energy estimation, the strategy built from a single linear program yields variance bounds up to 20–200% better than the optimized joint-measurement approach used as baseline."],"supporting_citations":[{"why":"Supplies the sample-complexity scaling law in terms of the parameter $\\delta$ that this paper computes and optimizes.","marker":"[14]"},{"why":"Shows that Clifford measurements achieve the fractional chromatic number bound, which turns exactness of the lower bound into a concrete optimal strategy.","marker":"[15]"},{"why":"Establishes the weighted beta number as a realization-independent graph parameter and introduces the BETA, STAB, and TH bodies used throughout the proof.","marker":"[24]"},{"why":"Provides the $\\hbar$-perfect classification, including the statement that every Pauli frustration graph on two qubits is $\\hbar$-perfect, which is load-bearing for Corollary 4.","marker":"[25]"},{"why":"Gives the optimized joint-measurement strategy for Hamiltonian estimation that serves as the baseline for the variance-bound comparisons.","marker":"[27]"},{"why":"Guarantees that every graph arises as the frustration graph of some set of Pauli observables, allowing the problem to be treated graph-theoretically.","marker":"[29]"},{"why":"Provides the state-polynomial optimization hierarchy used to compute the weighted beta number and hence to approximate $\\delta$ from above.","marker":"[49]"}],"fun_headline_variants":["Clifford measurements proven optimal for two-qubit shadow tomography","Clifford measurements are sample-optimal for Pauli shadow tomography","Two-qubit Clifford measurements achieve optimal shadow tomography","Graph parameters reveal optimal shadow tomography with limited resources"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper relies on a classification taken from the companion work: every Pauli anticommutation graph realizable on two qubits is $\\hbar$-perfect, meaning its $\\beta$ number equals its weighted independence number for all weights; this classification is cited rather than proved here, and the two-qubit Clifford-optimality claim fails if any two-qubit realization escapes it.","fun_headline_variants_meta":{"raw":{"variants":["Clifford measurements proven optimal for two-qubit shadow tomography","Clifford measurements are sample-optimal for Pauli shadow tomography","Two-qubit Clifford measurements achieve optimal shadow tomography","Graph parameters reveal optimal shadow tomography with limited resources"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001011,"raw_usage":{"total_tokens":4277,"prompt_tokens":959,"completion_tokens":3318,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":3264}},"tokens_in":575,"tokens_out":3318,"duration_ms":24055,"temperature":1.0,"reasoning_tokens":3264,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:36:59.670730+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all two-qubit Pauli realizations, compute for each resulting frustration graph the weighted $\\beta$ number via SDP and compare with the weighted independence number; finding any two-qubit graph with $\\beta(G,w)>\\alpha(G,w)$ for some weight vector $w$ would make the claimed Clifford optimality for two-qubit partitions false. Alternatively, on a concrete two-qubit partition compute $\\delta_\\tau$ by the SDP hierarchy and compare with $1/\\chi_f(G(\\tau))$; a gap would refute Corollary 4.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sample-complexity scaling law in terms of the parameter $\\delta$ that this paper computes and optimizes."},{"cited_title":"( 69) below to obtain the optimal {tI }","cited_arxiv_id":null,"evidence_quote":"Shows that Clifford measurements achieve the fractional chromatic number bound, which turns exactness of the lower bound into a concrete optimal strategy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the weighted beta number as a realization-independent graph parameter and introduces the BETA, STAB, and TH bodies used throughout the proof."},{"cited_title":"Busch, P","cited_arxiv_id":null,"evidence_quote":"Provides the $\\hbar$-perfect classification, including the statement that every Pauli frustration graph on two qubits is $\\hbar$-perfect, which is load-bearing for Corollary 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the optimized joint-measurement strategy for Hamiltonian estimation that serves as the baseline for the variance-bound comparisons."},{"cited_title":"Huang, R","cited_arxiv_id":null,"evidence_quote":"Guarantees that every graph arises as the frustration graph of some set of Pauli observables, allowing the problem to be treated graph-theoretically."}],"review_version":1}