{"id":"09fbfb53-9b23-4c64-b01e-6d41614d7aea","arxiv_id":"1908.05628","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"All elements of a qubit k-RDM can be measured with O(3^k log^{k-1} N) circuits, and all elements of a fermionic 2-RDM with O(N^2) circuits, matching a new Ω(N^2) lower bound for Clifford measurements.","lead":"Quantum computers that simulate molecules need many repeated measurements to read out their results; this paper designs schedules that group compatible measurements so far fewer runs are needed. It also proves a matching lower bound for fermionic systems, showing the proposed method is essentially the best possible under standard measurement assumptions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"App. H's lower-bound proof only covers direct measurement in a basis containing each operator; Clifford+CB protocols with classical post-processing are not ruled out, so the advertised optimality is broader than proven.","rationale":"The paper makes a genuinely useful contribution: the qubit binary-partition construction gives O(3^k log^(k-1) N) circuits, the fermionic pairing scheme gives O(N^2) circuits with local O(N)-depth measurement circuits, and the OpenFermion implementation is concrete evidence of the constructive claims. The lower bound is the linchpin of the advertised optimality, and the gap is real. The reader's weakest assumption identifies the same issue: App. H's inference step is only valid for direct measurement scheduling, not for all Clifford+CB protocols with classical post-processing. The good-faith reading of the abstract and Section III is that the paper's intended scope is measurement scheduling for direct estimation, in which case the upper and lower bounds are consistent up to a constant factor. But Theorem 1 as worded claims more, and the conclusion overstates the generality of the optimality result. The factor-4 variance error and the factor 5/2 between the O(N^2) construction and the 4/3 N^2 lower bound are real but do not affect the asymptotic claim. Since the issue is an overgeneralized theorem statement and proof scope, not a failure of the constructive results, the appropriate final verdict remains conditional, matching the reader's assessment.","tokens_in":18561,"tokens_out":12084,"duration_ms":135357,"concrete_test":"Implement a classical-shadow estimator for all 4-Majorana operators of an N-mode fermionic state, using random Clifford circuits acting on a Bravyi-Kitaev encoding, and also using random matchgate/fermionic Gaussian circuits. Compute the shadow-norm sample-complexity bound for N = 8, 16, 32, 64 at fixed target error, and fit the number of preparations to N^alpha. If alpha < 2 for either family, Theorem 1 is false as stated; if alpha >= 2, the conclusion survives but App. H still needs a revised proof that does not assume each operator is directly measured.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of asymptotic optimality rests on Theorem 1 in App. H, but the proof implicitly assumes that estimating an expectation value <Gamma_i> requires M_i preparations in a basis containing Gamma_i. This is the direct-measurement model. A fixed Clifford circuit followed by computational-basis readout is indeed equivalent to measuring a commuting set {U^dagger Z_j U}, and App. H correctly shows this. However, protocols with classical post-processing, such as classical shadows, can combine shots from many random Clifford circuits and estimate expectation values of Pauli operators that are not contained in any individual measured clique. The counting bound from App. B, clique size at most (N choose k), therefore lower-bounds only the number of direct basis-containing measurements, not the number of preparations for all Clifford+CB estimation protocols. Since the theorem is stated as a general lower bound on preparations and is used to justify both asymptotic optimality and the exponential separation from qubit k-RDMs, this is a load-bearing gap. The variance bound in Eq. H1 also misses a factor of 4, though that affects only constants and is secondary.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the measurement bottleneck in partial tomography of quantum states for variational quantum eigensolvers, focusing on scheduling measurements of k-body reduced density matrices (k-RDMs). For qubit k-RDMs, it constructs a set of Pauli-word measurement circuits via binary/ary partitioning and proves a bound of O(3^k log^{k-1} N) unique circuits. For fermionic k-RDMs, it proves in Theorem 1 a lower bound of Ω(ε^{-2}N^k) state preparations for Clifford circuits followed by computational-basis measurement and gives a construction that directly measures all elements of the fermionic 2-RDM in O(N^2) circuits using Majorana pairings and swap networks. It further presents a method to estimate arbitrary linear combinations of anti-commuting 4-Majorana operators with O(N^4/ω) circuits and circuit depth O(ω), and proves a bound of 2N+1 on the maximum size of anti-commuting Pauli/Majorana cliques. The paper claims asymptotic optimality of the fermionic 2-RDM scheme and an exponential separation between the number of circuits required for qubit versus fermionic RDMs.","tokens_in":18744,"tokens_out":17479,"duration_ms":158608,"significance":"The paper contains useful and partly novel constructions: the qubit k-RDM scheme is an exponential improvement over the earlier O(N^k) direct-measurement approaches, the fermionic 2-RDM construction is explicit, uses only linear connectivity with O(N)-depth circuits, is accompanied by code in OpenFermion, and supports symmetry-verification error mitigation. The anti-commuting linear-combination method provides a practical trade-off between circuit depth and number of measurements. If the lower bound were valid in full generality, the optimality claim would be a significant result. As it stands, the upper-bound scheduling schemes are solid, but the advertised asymptotic optimality and exponential separation are proven only for direct-measurement protocols, which limits the scope of the main claim.","major_comments":[{"comment":"The proof of Theorem 1 assumes that estimating ⟨Γ_i⟩ requires M_i preparations in a basis containing Γ_i (App. H, first paragraph). This is the direct-measurement model. For a fixed Clifford circuit with computational-basis readout, that is correct. However, the theorem is stated as a lower bound on the number of preparations for any Clifford-plus-computational-basis protocol, and that class includes protocols with classical post-processing (classical shadows being a concrete example) that estimate many non-commuting expectation values from the same random data. The counting bound in App. B lower-bounds the number of direct basis-containing measurements, not the total number of preparations for all estimation strategies. Since Theorem 1 is used to conclude asymptotic optimality of the O(N^2) fermionic 2-RDM scheme and the exponential separation from qubit k-RDMs, this is a load-bearing gap. The theorem should either be restricted to direct-measurement schemes or the proof extended to rule out post-processing estimators.","section":"Theorem 1 (Sec. III) / App. H"},{"comment":"The proof of the 2N+1 upper bound on anti-commuting cliques has a gap for odd n. The text claims that the union of the even-parity subsets P_⃗b is the set of operators commuting with ∏_{P_i∈S}P_i and therefore has size exactly half of P_N. If the product ∏P_i is proportional to the identity (e.g., S={X,Y,Z} for N=1), its centralizer is all of P_N, so the claimed half-size statement is false and the subsequent counting of the set anticommuting with all elements of S becomes invalid. The theorem itself is true, but the proof needs repair.","section":"App. G"}],"minor_comments":[{"comment":"The variance bound is off by a factor of 4: for a ±1-valued random variable with mean μ, the variance of the sample mean after M_i shots is (1-μ^2)/M_i, not (1-μ^2)/(4M_i). This affects only constants, since the theorem is asymptotic.","section":"App. H, Eq. (H1)"},{"comment":"The conclusion states the fermionic lower bound as Ω(N^{⌈k/2⌉}), which is inconsistent with Theorem 1 and the introduction, both of which state Ω(N^k). This should be corrected.","section":"Sec. V"},{"comment":"The expression for the total number of cliques, `∑_{n'=1}^{⌈logN⌉} N^2 n' + ...`, appears to contain a typo: as written the first term would contribute ~N^2 log N rather than ~N^2, and the stated ∼10/3 N^2 scaling would not follow. Please clarify the intended summation.","section":"App. C, Eq. (C5)"},{"comment":"The last line of Eq. (F4) should read cos(θ)P_j − sin(θ)P_i; as printed it has −sin(θ)P_j, which is inconsistent with the standard rotation between two anti-commuting Pauli operators.","section":"App. F, Eq. (F4)"}],"recommendation":"major_revision","confidential_remarks":"The paper's main combinatorial upper bounds are likely correct and useful, but the overstatement of Theorem 1 is a genuine scope issue: the proof only covers direct-measurement protocols, while the theorem claims to bound all Clifford-plus-readout estimation protocols. The authors can likely fix this by restating the lower bound for direct measurement and adjusting the optimality/exponential-separation claims accordingly. The App. G proof gap is also fixable. I see no grounds for rejection if these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper deserves a serious referee, but the framing oversells the lower bound. The real substance is the constructive part: a binary-partition scheme for qubit k-RDMs using O(3^k log^{k-1} N) circuits, a Majorana-pairing scheme for the fermionic 2-RDM using O(N^2) circuits with O(N) depth on a linear array, and a counting bound of Omega(N^k) commuting cliques for fermionic k-RDMs. There is also a nice construction for measuring anti-commuting linear combinations with O(omega) gates, and the code is shipped in OpenFermion. The asymptotic upper bounds look correct, and the prior-art table is genuinely useful.\n\nThe soft spot is Theorem 1. The proof shows that if you insist on estimating each operator by repeatedly preparing and measuring in a basis that contains it, you need Omega(eps^-2 N^k) preparations. That is a valid direct-measurement model. But the theorem is stated as a general lower bound on Clifford circuits plus computational-basis readout. That is broader than the proof supports. A classical-shadows protocol uses random Clifford measurements and classical post-processing to estimate many non-commuting Pauli expectation values from the same shots; it is not measuring each operator in a basis containing it. The clique-size bound does not touch such protocols. So \"asymptotically optimal\" is established for direct measurement scheduling, not for all Clifford+CB tomography. The paper should be revised to say that explicitly.\n\nSecondary issues are minor by comparison. Eq. H1 misses a factor of 4 in the variance, which only affects constants. The conclusion states the lower bound as Omega(N^{ceil(k/2)}) while the abstract and Theorem 1 say Omega(N^k); that is a typo, but it will confuse readers. The qubit k-RDM scheme is honestly acknowledged as equivalent to Cotler and Wilczek for k=2, and the paper is upfront about the open factor of 5/2 in the fermionic 2-RDM clique cover.\n\nBottom line: the upper bounds are solid, the lower bound is correct within its model, and the practical impact for VQE-style algorithms is real. The authors need to narrow the theorem statement and fix the constants before publication, but this is exactly the kind of work that should get referee time.\n\nBest,\n[Your name]","headline":"Useful upper bounds and a genuinely practical fermionic 2-RDM scheme, but the optimality claim is broader than the proof: the lower bound only covers direct measurement in a basis containing each operator, not all Clifford-plus-readout protocols.","tokens_in":19324,"tokens_out":3299,"would_cite":true,"duration_ms":32880,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that all elements of the fermionic 2-RDM can be estimated with $O(N^2)$ circuits, that this is asymptotically optimal among Clifford-based direct measurement schemes, and that qubit $k$-RDMs need only $O(3^k \\log^{k-1}…","keywords":["quantum state tomography","reduced density matrices","measurement scheduling","commuting cliques","Majorana operators","Pauli words","variational quantum eigensolver","near-term quantum computation"],"falsifier":"Exhibit a concrete protocol that estimates every element of the fermionic 2-RDM to fixed error with $o(\\epsilon^{-2} N^2)$ state preparations—for instance a shadow-style scheme using random Clifford measurements and classical post-processing—or a direct commuting-clique protocol that covers all 4-Majorana operators with fewer than $\\frac{4}{3}N^2 - \\frac{8}{3}N + 1$ unique circuits; either would break the claimed optimality.","tokens_in":18358,"feed_emoji":"⚛️","tokens_out":9765,"duration_ms":90244,"temperature":0.7,"pith_summary":"How many distinct measurement circuits does it take to characterize the local correlations of an $N$-qubit or $N$-fermion state? This paper gives near-optimal answers. For qubit systems, all $k$-body reduced density matrix ($k$-RDM) elements can be directly measured using $O(3^k \\log^{k-1} N)$ unique circuits, an exponential improvement in $N$ over prior art. For fermionic systems—the relevant case for quantum chemistry—all elements of the 2-RDM can be measured with only $O(N^2)$ circuits using a linear-depth Clifford measurement circuit, and the paper proves this is asymptotically optimal for schemes built from Clifford circuits and computational-basis readout. It also gives a tunable scheme that measures any linear combination of fermionic 2-RDM elements with $O(N^4/\\omega)$ circuits of $O(\\omega)$ gates, trading shot count against circuit depth.","feed_headline":"Fermionic 2-RDM measurement hits optimal O(N^2) circuits","feed_subtitle":"A new scheduling scheme cuts quantum-chemistry measurement cost from O(N^4) to O(N^2) in system size.","key_machinery":"The load-bearing object is the commuting clique: a set of operators that can be estimated from one state preparation because a single measurement basis contains them all. The paper's qubit result is carried by a binary-partition construction that assigns each qubit a Pauli letter so that every tensor product of $k$ Paulis appears in at least one word. The fermionic result is carried by pairings of the $2N$ Majorana operators: each pairing of $N$ disjoint pairs generates a maximal commuting clique of products of $k$ pairs, and a divide-and-conquer iteration over block pairings covers every 4-Majorana operator in $O(N^2)$ cliques. The anti-commuting result is carried by the rotation $e^{\\theta P_i P_j}$, which rotates between two anti-commuting Pauli or Majorana operators while leaving the rest of an anti-commuting clique fixed, allowing a linear combination to be compressed into one measurable Pauli operator.","core_discovery":"The central claim is a pair of asymptotic results plus a lower bound. First, any $k$-qubit RDM can be tomographed by assigning each qubit a Pauli letter $X$, $Y$, or $Z$ in a carefully chosen set of words, with only $O(3^k \\log^{k-1} N)$ words needed to contain every $k$-local Pauli product. Second, every element of the fermionic 2-RDM can be directly measured using $O(N^2)$ unique commuting cliques of 4-Majorana operators, implemented by a Clifford basis change that permutes Majorana labels in depth $O(N)$; the paper proves a matching lower bound $\\Omega(\\epsilon^{-2} N^k)$ on the number of state preparations for any Clifford-circuit protocol estimating a fermionic $k$-RDM, making the 2-RDM scheme asymptotically optimal and establishing an exponential separation between qubit and fermionic tomography. Third, a set of mutually anti-commuting Majorana operators can be rotated into a single Pauli operator for readout, so a linear combination of 2-RDM elements can be sampled in $O(N^4/\\omega)$ circuits each of depth $O(\\omega)$.","pith_inferences":["Because the lower bound excludes indirect estimation, the paper leaves open whether shadow-style random measurements could estimate the fermionic 2-RDM with fewer than $\\Omega(N^2)$ preparations; if they could, the exponential separation would hold for direct scheduling but not for tomography in general.","The anti-commuting compression technique is not obviously limited to 2-RDM elements: any sparse fermionic operator expressed as a short linear combination of Majorana products could be sampled with the same depth-versus-shots trade-off, which may extend the result beyond chemistry.","The qubit scheme's polylogarithmic word count suggests a natural randomized variant: sample words from the binary-partition distribution and use median-of-means post-processing, which could turn the deterministic clique cover into a shadow-style estimator with comparable scaling.","For small molecule sizes, the exact clique counts rather than asymptotics matter; the paper reports implementations of its measurement generation, so a practical benchmark on realistic molecular Hamiltonians would clarify when the $O(N^2)$ regime actually begins."],"forward_implications":["For qubit systems, partial tomography of $k$-local correlations becomes practical for large $N$, since the number of circuits grows only polylogarithmically in $N$.","For fermionic systems, estimating the 2-RDM—and hence energies and gradients in quantum chemistry—drops from a quartic to a quadratic number of circuits, directly reducing the wall-clock cost of variational quantum algorithms.","The lower bound means no Clifford-circuit direct measurement protocol can beat the $O(N^2)$ fermionic 2-RDM scheme asymptotically; further speedups must come from a different measurement model.","The $O(N^4/\\omega)$ anti-commuting scheme gives near-term devices a tunable trade-off: fewer shots at the price of deeper circuits, or much shallower circuits at the price of more shots.","When the Hamiltonian has symmetries, the clique count drops further by a factor that depends on the number of symmetries, and the measurement circuits conserve parity, enabling symmetry-verification error mitigation at no extra cost."],"supporting_citations":[{"why":"Defines the variational hybrid quantum-classical setting and establishes partial-tomography measurement cost as a bottleneck.","marker":"[2]"},{"why":"Introduces fermionic and qubit k-RDMs and the quantities estimated from them, such as energy and gradients.","marker":"[13]"},{"why":"Formulates measurement optimization as a minimum clique cover, the prior-art heuristic baseline the paper improves on.","marker":"[19]"},{"why":"Gives the unitary-partitioning approach and the numerical observation of $\\Omega(N^3)$ anti-commuting cliques that the paper proves.","marker":"[24]"},{"why":"Provides the prior basis-rotation grouping scheme with $O(N)$ fermionic circuits and motivates the lower circuit complexity for linear combinations.","marker":"[26]"},{"why":"Supplies the fermion-to-qubit encoding used to turn Majorana-pair measurements into local qubit readouts.","marker":"[32]"},{"why":"Supplies the parallel sorting network that makes the Majorana swap measurement circuit depth $O(N)$ on a linear array.","marker":"[33]"}],"fun_headline_variants":["Optimal fermionic 2-RDM tomography in O(N^2) circuits","Exponential quantum simulation speedup: O(N^2) for fermionic 2-RDM","Direct fermionic 2-RDM measurement: exponential gain, optimal circuits","O(N^2) circuits for fermionic 2-RDM: optimal and proven"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of optimality assumes a measurement protocol is a Clifford circuit followed by computational-basis readout, so that each preparation can only estimate expectation values of mutually commuting operators; it does not cover indirect estimation schemes, such as classical shadows, that reconstruct many non-commuting expectation values from random measurements by classical post-processing.","fun_headline_variants_meta":{"raw":{"variants":["Optimal fermionic 2-RDM tomography in O(N^2) circuits","Exponential quantum simulation speedup: O(N^2) for fermionic 2-RDM","Direct fermionic 2-RDM measurement: exponential gain, optimal circuits","O(N^2) circuits for fermionic 2-RDM: optimal and proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000951,"raw_usage":{"total_tokens":4134,"prompt_tokens":1102,"completion_tokens":3032,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":2943}},"tokens_in":718,"tokens_out":3032,"duration_ms":23143,"temperature":1.0,"reasoning_tokens":2943,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:08:56.397431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a concrete protocol that estimates every element of the fermionic 2-RDM to fixed error with $o(\\epsilon^{-2} N^2)$ state preparations—for instance a shadow-style scheme using random Clifford measurements and classical post-processing—or a direct commuting-clique protocol that covers all 4-Majorana operators with fewer than $\\frac{4}{3}N^2 - \\frac{8}{3}N + 1$ unique circuits; either would break the claimed optimality.","supporting_citations":[{"cited_title":"Pauli heuristic - O(N 4) - - O(1) - - -","cited_arxiv_id":null,"evidence_quote":"Defines the variational hybrid quantum-classical setting and establishes partial-tomography measurement cost as a bottleneck."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces fermionic and qubit k-RDMs and the quantities estimated from them, such as energy and gradients."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates measurement optimization as a minimum clique cover, the prior-art heuristic baseline the paper improves on."},{"cited_title":"Pauli clique cover Pauli evolutions O(N 3) O(N 2 logN) - O(N 8−N 12) full no no","cited_arxiv_id":null,"evidence_quote":"Gives the unitary-partitioning approach and the numerical observation of $\\Omega(N^3)$ anti-commuting cliques that the paper proves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the prior basis-rotation grouping scheme with $O(N)$ fermionic circuits and motivates the lower circuit complexity for linear combinations."},{"cited_title":"Reducibility among combinatorial prob- lems,","cited_arxiv_id":null,"evidence_quote":"Supplies the fermion-to-qubit encoding used to turn Majorana-pair measurements into local qubit readouts."}],"review_version":1}