{"id":"cd0c02ef-f602-41ee-9350-b245ab1e452c","arxiv_id":"2505.00698","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"New adaptive quantum gradient estimation variants (Method I and Method II) achieve O~(N^{k/2})/epsilon state-preparation queries for fermionic k-RDMs, and a sine-state amplitude estimation circuit is shown to be near-optimal in mean squared error.","lead":"This paper analyzes and extends quantum algorithms that estimate many properties of a quantum state at the Heisenberg limit, proposing symmetry-based and parallel variants that reduce the number of state-preparation calls. The authors report the best-known asymptotic query complexity for estimating fermionic k-particle reduced density matrices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's concentration bound is algebraically wrong: the stated σ_Δ satisfies the Bernstein requirement only when σ_Δ≤2, but the paper's own FeMo parameters give σ_Δ≈374 versus the required root ≈406; the query-complexity theorems inherit this gap.","rationale":"The Reader correctly identified an unproved smallness assumption in Lemmas 5/7, but that particular gap is less decisive: the circuit V(q) is separable and consists essentially of single-qubit phase rotations controlled by the classically known u_j, so a rigorous δ_V bound is straightforward to supply. The more serious problem is in the concentration step that defines σ_Δ, because σ_Δ directly sets the Hamiltonian simulation time Q and therefore the total query complexity in Theorems 2/4 and Lemmas 12/13. The proof's own algebra requires t to be at least the root of a quadratic, but the stated σ_Δ is too small for the parameter regime used in the numerical study. Algorithm 5 appears to compensate by using a different, larger formula (4v instead of 2v), which suggests the paper's theorem statements and its numerical evaluation are inconsistent. This is an internal correctness issue rather than a disagreement with consensus. The asymptotic O~(N^{k/2}) might survive once σ_Δ is corrected, and the numerical ranking in Fig. 8 may be robust, so REJECT is not warranted; however, the central resource claims cannot be accepted as proven until Lemma 4 and its parallel analogue are repaired. The recommended verdict stays CONDITIONAL, with the condition explicitly including a corrected concentration bound.","tokens_in":69987,"tokens_out":24673,"duration_ms":256627,"concrete_test":"Re-derive Lemma 4's Bernstein step: with L=log(2mΔ/δ'), v=E[(2X)^2], and Σ = max_λ Σ_j ||O_j^(λ)||^2, check whether σ_Δ from Eq. (118) satisfies σ_Δ^2 - (2L/3)σ_Δ - 2LvΣ ≥ 0. Plug in the paper's own FeMo 1-RDM numbers (N=152, η=113, k=1, δ'=2^{-10}, v=0.1652): the left-hand side is negative. Then recompute Algorithms 5 and 6 using the corrected root σ_Δ^corr = L/3 + sqrt(L^2/9 + 2LvΣ), and verify whether Method II still has the lowest query count in Fig. 8 at ε=10^{-3}; if the corrected counts shift the ordering or change the claimed gaps, the numerical conclusions need revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing gap is not the δ_V smallness assumption in Lemmas 5/7; V is a product of single-qubit Z rotations and can be made exact or exponentially precise without U_ψ queries. The critical flaw is the matrix Bernstein step in Lemma 4 (and its parallel analogue Lemma 7), which underpins the amplified block-encoding used in Theorems 2/4 and hence Lemmas 12/13. With L=log(2mΔ/δ'), v=E[(2X)^2], and Σ = max_λ Σ_j ||O_j^(λ)||^2, the proof requires t=σ_Δ to satisfy t^2 - (2L/3)t - 2LvΣ ≥ 0. The exact threshold is t ≥ L/3 + sqrt(L^2/9 + 2LvΣ). The paper instead sets σ_Δ = sqrt(2vLΣ + 4L/3); substituting gives (2L/3)(2-σ_Δ) ≥ 0, which holds only for σ_Δ ≤ 2. For the paper's FeMo 1-RDM parameters (N=152, η=113, k=1, δ'=2^{-10}, v=0.1652), σ_Δ from Eq. (118) is ≈374, while the required root is ≈406. Algorithm 5 silently uses 4v inside the square root instead of 2v, which is a different formula and does not match the stated lemma. Thus the amplification lemma is not proven as stated, and the total query counts in Fig. 8 and Table 2 rest on an invalid concentration inequality. The asymptotic O~(N^{k/2}) may survive a correction, but the proof must be repaired before the resource claims are accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops Heisenberg-limited quantum algorithms for estimating the expectation values of many bounded observables from a pure state, with a focus on fermionic k-RDMs. It revisits QAE with a sine-state probe, proves an MSE bound for that circuit, and then generalizes the adaptive QGE framework of Ref. [32]. Two variants are proposed: Method I exploits symmetry via subspace QSVT, and Method II further parallelizes the probe register. The central claimed result is that Method II estimates all elements of the k-RDM with root-MSE epsilon using O~(sqrt(C(eta,k) C(N-eta+k,k)))/epsilon queries to the state-preparation oracle, i.e., O~(N^{k/2})/epsilon for fixed filling, which is quartic better than QAE-based estimation and quadratic better than the previous adaptive QGE. The paper also contains a detailed numerical comparison for the FeMo cofactor and Fermi-Hubbard models, together with explicit algorithms for computing the query counts.","tokens_in":70355,"tokens_out":7349,"duration_ms":70342,"significance":"If the main resource claims hold, this is a substantial advance: it would establish a new asymptotic benchmark for fermionic reduced-density-matrix estimation and give the best query counts among compared algorithms in the high-precision regime. The paper has real strengths: Lemma 1 and Lemma 2 are clean and self-contained; Lemma 11 provides a combinatorial norm bound for k-RDM observables that is central to the speedup; and the numerical study is detailed, falsifiable, and directly comparable across methods. The core adaptive-QGE framework (Theorem 1) is sound and the presentation of the algorithms is largely reproducible. However, several load-bearing steps are not rigorously established, and one concentration argument in the proof of Lemma 4 appears algebraically incorrect. These gaps directly affect the validity of the stated query-complexity theorems and the numerical query counts, so the central claims cannot be accepted in the present form.","major_comments":[{"comment":"The matrix Bernstein step in Lemma 4 is not proved as stated. With L = log(2 m_Delta / delta'), the requirement for the tail bound exp[-t^2 / (2 v Sigma + 2 t/3)] <= delta'/(2 m_Delta) is t^2 - (2L/3)t - 2L v Sigma >= 0, whose exact threshold is t >= L/3 + sqrt(L^2/9 + 2 L v Sigma). The paper instead sets sigma_Delta = sqrt(2 v L Sigma + 4L/3). Substituting this value gives (2L/3)(2 - sigma_Delta) >= 0, which holds only when sigma_Delta <= 2. For the FeMo 1-RDM parameters used in Section VID (N=152, eta=113, k=1, delta'=2^{-10}, v=0.1652 and the bound from Lemma 11), Eq. (118) gives sigma_Delta ~ 374, whereas the required root is ~406. Thus Lemma 4 does not establish the existence of the amplified block-encoding, and the query-complexity claims that inherit from it (Theorems 2 and 4, Lemmas 12 and 13) are not justified. In addition, Algorithm 5, Eq. (233), uses 4v inside the square root, while Lemma 4, Eq. (118), uses 2v; the numerical evaluation is therefore based on a formula that is not the one stated in the supporting lemma. This needs a corrected proof and consistent constants.","section":"Section VB, Lemma 4 (Eqs. (117)-(118), proof near Eq. (129))"},{"comment":"The final inequality in the proof of Lemma 5, epsilon'' + sqrt(2 epsilon'') + sqrt(5 delta') + delta_V < 1/12, is numerically false for the constants stated in the lemma. The lemma fixes delta' = 2^{-10} and the proof sets epsilon'' = 2^{-10}, giving 2^{-10} + sqrt(2 * 2^{-10}) + sqrt(5 * 2^{-10}) ~ 0.115, which exceeds 1/12 ~ 0.0833. The Euclidean-distance guarantee of Lemma 5 and the resulting failure probability mu = 0.011 + 1/12 in the proof of Theorem 2 therefore do not follow. Either different constants must be chosen or the error budget must be reworked; this is load-bearing because the sample complexity R(q) and the total query count depend on this distance bound.","section":"Section VB, proof of Lemma 5 (Eq. (144))"},{"comment":"Both Lemma 5 and Lemma 7 assume that the circuit V^(q) subtracting the running estimates u_j is implemented with error delta_V 'sufficiently small' against epsilon'' and delta', but no explicit bound on delta_V is derived. The statements that V^(q) is separable and 'expected' to be precise are not a proof, and the final distance bounds in Eqs. (144) and (182) depend on this unproved assumption. Similarly, Lemma 6 is given only as a sketch and Theorem 4 is stated with a sketch of proof that invokes an integrated version of Lemmas 4 and 6 without a complete derivation. Since Method II and the associated O~(N^{k/2})/epsilon claim rest on these results, the manuscript should provide full proofs or clearly state the missing steps as assumptions.","section":"Section VB/VD, Lemmas 5 and 7, and Theorem 4"},{"comment":"The claim that the sine state is 'nearly optimal' for the QAE circuit is supported only by numerical minimization of the quadratic form for q = 8 and q = 9 (Fig. 3); there is no analytic bound on the gap between the sine-state MSE and the optimal-state MSE. Lemma 1 proves an upper bound on the MSE for the sine state, but the near-optimality statement is not a theorem. This does not affect the main k-RDM resource claims, but it is part of the paper's stated contributions and should be qualified accordingly.","section":"Section IIIA, sine-state near-optimality"}],"minor_comments":[{"comment":"There are several typos and notational inconsistencies: 'Holvevo' should be 'Holevo'; the bracket notation in Eq. (6) appears as '\\MSE' rather than a properly defined symbol; and the phrase '2Q uses of U_psi or U_psi^dagger' in Lemmas 5 and 7 should specify whether the count includes both the forward and inverse oracles. These do not change the technical content but should be cleaned up.","section":"Throughout"},{"comment":"The table would be easier to interpret if the column 'Space Complexity' explicitly included the ancilla costs for the QAE and QGE methods as stated in the text, since some entries list only the main register size. Clarifying the counting convention would help readers reproduce the comparison.","section":"Section VIA, Table 2"},{"comment":"The numerical algorithms use a slightly modified error threshold (c = 1/(80(1+pi)^2) and q_max = ceil(log2(1/(sqrt(40/11) epsilon)))) that is explained in the text, but the derivation would be clearer if the intermediate display in Eq. (231)-(232) were referenced directly at the point where the parameter c is introduced. Additionally, the function HS_DEGREE should state its return convention when the bracketing loop terminates.","section":"Section VI, Algorithms 5 and 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is a companion to the letter arXiv:2505.00697 and reuses the proof architecture of Ref. [32]. The core ideas are promising, and I do not see a circularity problem: the new estimates are derived from stated assumptions and norm bounds rather than from previously fitted values. The main obstacle is that Lemma 4's concentration step is not valid as written and the constants in Lemma 5's final inequality do not close the triangle inequality. These are technical but load-bearing; I expect they can be repaired with a correct matrix-Bernstein threshold and a consistent choice of epsilon'', delta', and epsilon', but the current manuscript's resource claims are not supported until that is done."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the QAE section is genuinely good: Lemma 1 derives the sine-state MSE as (π/2^{q+1})² + O(2^{-3q}) with explicit constants and a circuit that halves the oracle queries, and the companion result that the uniform-superposition probe only reaches the SQL is clean and correct. Second, the k-RDM headline — O~(N^{k/2})/ε for Methods I and II — rests on Lemma 4, and Lemma 4 has a real algebraic error in its matrix Bernstein step.\n\nThe stress-test note checks out on the substance. The proof requires t ≥ L/3 + sqrt(L²/9 + 2LvΣ); substituting the paper's σ_Δ = sqrt(2vΣL + 4L/3) into t² − (2L/3)t − 2LvΣ ≥ 0 gives (2L/3)(2 − σ_Δ) ≥ 0, which holds only for σ_Δ ≤ 2. Under the paper's own FeMo 1-RDM parameters σ_Δ is a few hundred and the required root is larger by roughly (2/3)L. So the claim that t = σ_Δ suffices, justified by sqrt(a+b) ≤ sqrt(a) + sqrt(b), is wrong: that subadditivity bound goes in the wrong direction for this purpose. Theorems 2 and 4, Lemmas 12 and 13, and the numbers in Fig. 8 and Table 2 all inherit the gap. I would bet the O~(N^{k/2}) scaling survives a repair — the missing term is logarithmic and the construction is otherwise plausible — but the theorem as stated is not proven. One detail in the stress-test note is off: Algorithm 5's 4v is not a silent inconsistency; it is Lemma 4's 2v multiplied by the factor-2 bound from Lemma 11. The flaw is in Lemma 4 itself.\n\nThe reader's flagged δ_V assumption in Lemmas 5 and 7 is real but mild: V^(q) is a product of single-qubit Z rotations, so it can be made exact or exponentially precise with no U_ψ queries; the authors should just state that. The bigger structural issue is that Lemma 6 and Theorem 4 are explicitly sketches, so the headline Method II claim is not fully proved. The sine-state near-optimality in QAE is numerically demonstrated, not proven — the paper is honest about that. No code or data were shipped, but the query counts are deterministic from the stated formulas, so the numerics are reimplementable.\n\nCredit where due: Theorem 1's adaptive framework with per-iteration failure budget δ(q) = c/8^{qmax−q} is clean; Lemma 11's combinatorial bound Σ_j O_j² ≤ 2 C(η,k) C(N−η+k,k), with the Vandermonde identity in Appendix D4, is real work and looks correct; and the authors clearly label the sketch proofs rather than burying them.\n\nWho this is for: anyone estimating resources for fermionic partial tomography on early fault-tolerant hardware, and anyone tracking Heisenberg-limited multi-observable estimation. The QAE section is worth reading on its own. It deserves a serious referee — the paper is substantial and the flaw is reparable — but the expectation should be major revision. I would not cite the k-RDM resource claims until Lemma 4 is repaired; the sine-state MSE result is citable independently.","headline":"Sine-state QAE analysis is clean and worth reading; the k-RDM resource claims lean on a matrix Bernstein step in Lemma 4 that is algebraically wrong, though the asymptotics likely survive a repair.","tokens_in":70926,"tokens_out":13864,"would_cite":false,"duration_ms":124734,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":["03.67.Ac","03.67.Lx"],"model":"deepseek-v4-flash","headline":"An adaptive symmetry-aware quantum scheme estimates all fermionic k-RDM elements with query cost ~N^{k/2}/ε at fixed particle number.","keywords":["quantum amplitude estimation","quantum gradient estimation","Heisenberg limit","fermionic k-RDM","adaptive estimation","quantum signal processing","subspace QSVT","query complexity"],"falsifier":"To falsify the central claim, one would need to exhibit an implementation of the estimate-subtraction circuit $V^{(q)}$ for a concrete instance (for example, the FeMo-cofactor 2-RDM at ε = $10^{{-3}}$) and compute its approximation error $\\delta_V$; if $\\delta_V$ is not much smaller than $\\varepsilon''$ ($2^{{-14}}$ in Method I, $(\\delta(q))^2/26$ in Method II), the Euclidean-distance bound of $1/12$ (or $E$) fails, and with it the proofs of the query-complexity theorems. More directly, a numerical simulation that counts queries including $V^{(q)}$ and shows the root MSE exceeds ε would settle the claim.","tokens_in":69743,"feed_emoji":"⚛️","tokens_out":9582,"duration_ms":95539,"temperature":0.7,"pith_summary":"This paper establishes that an adaptive quantum gradient estimation (QGE) algorithm, enhanced by symmetry and by preparing multiple probe copies in parallel, estimates all elements of a fermionic k-body reduced density matrix (k-RDM) with root-mean-square error ε using $\\widetilde O(\\sqrt{C(\\eta,k)C(N-\\eta+k,k)})/\\epsilon$ queries to the state preparation oracle. For a fixed particle number η, this is $O(N^{k/2})/\\epsilon$, a quartic improvement over the $O(N^{2k})/\\epsilon$ cost of quantum amplitude estimation (QAE) and a quadratic improvement over the earlier adaptive QGE bound $O(N^{k+1/2})/\\epsilon$. The paper also proves that a QAE circuit using a sine-state probe achieves Heisenberg-limited mean squared error $(\\pi/2^{q+1})^2$ with only $2q+1$ oracle queries, nearly saturating the lower bound, whereas the uniform-superposition probe attains only the standard quantum limit. The practical relevance is an explicit numerical comparison on the FeMo cofactor and the 7/8-filled Fermi-Hubbard model in which the proposed Method II has the lowest state-preparation query count for 1- and 2-RDMs at ε ≤ $10^{{-3}}$.","feed_headline":"Adaptive QGE scheme cuts k-RDM query cost to ~N^{k/2}/ε","feed_subtitle":"Quadratic improvement over prior QGE and quartic over amplitude estimation for fermionic k-body observables.","key_machinery":"The central object is the generalized adaptive QGE framework of Algorithm 1, which estimates the binary expansion of each expectation value by repeatedly preparing a probe state whose phase encodes the residual $\\langle O_j\\rangle - \\tilde u_j^{(q)}$. For fermionic k-RDMs, the load-bearing identity is Lemma 11: within the η-particle sector the projected observables satisfy the squared-sum bound $2\\binom{\\eta}{k}\\binom{N-\\eta+k}{k}$. Because the probe-state cost scales with the square root of this sum, the binomial bound directly produces the $\\widetilde O(N^{k/2})/\\epsilon$ scaling. Method I implements the probe by restricting uniform singular value amplification and quantum singular value transformation to symmetry sectors (subspace QSVT); Method II entangles R(q) copies of the probe register into one circuit, so that a single larger state preparation supplies all repetitions. The probe state itself is a cosine-weighted grid state, chosen because its per-measurement failure probability (0.011 for p=3) is much lower than the uniform state's 0.18.","core_discovery":"On its own terms, the paper's central claim is that the query complexity of estimating multiple observables at the Heisenberg limit can be dramatically reduced by combining three ingredients: adaptive bit-by-bit estimation of expectation values, a cosine-shaped probe state instead of a uniform superposition, and restriction to symmetry sectors of the target state. For fermionic k-RDMs, the observables are particle-number conserving and the sum of their squares within the η-particle sector is bounded by $2\\binom{\\eta}{k}\\binom{N-\\eta+k}{k}$. Because the QGE probe-state cost scales with the square root of that sum, Methods I and II obtain $\\widetilde O(\\sqrt{C(\\eta,k)C(N-\\eta+k,k)})/\\epsilon$ queries. Method II refines Method I by entangling R(q) copies of the probe register into a single circuit, replacing an R(q)-fold repetition of state preparation by one larger preparation and reducing the logarithmic factor in the number of observables. The paper further claims that QAE with a sine state reaches near-optimal MSE with $2q+1$ queries, and that expectation-value estimation through it requires $O(1)/\\epsilon$ queries to the state preparation unitary.","pith_inferences":["If the open $\\delta_V$ point is resolved, the same reduction should transfer to any symmetry-restricted observable family, because the query count is governed by the square root of the sum of squared projected observables.","The sine-state QAE result suggests that any phase-estimation-style circuit can saturate the constant-factor Heisenberg limit when the probe is chosen from the sine family, which may translate into practical gains for amplitude-estimation and Monte Carlo subroutines.","The parallel-probe trick trades logarithmic qubit overhead for a quadratic reduction in the number of state-preparation repetitions; this is a general design pattern for algorithms that would otherwise repeat independent estimates."],"forward_implications":["Method II estimates all fermionic k-RDM elements with query complexity $\\widetilde O(\\sqrt{C(\\eta,k)C(N-\\eta+k,k)})/\\epsilon$, so for fixed filling the scaling is $\\widetilde O(N^{k/2})/\\epsilon$.","This is a quartic improvement over QAE-based estimation and a quadratic improvement over the earlier adaptive QGE algorithm for k-RDMs.","In the FeMo cofactor numerical study, Method II has the lowest query count for 1- and 2-RDM estimation when ε ≤ 10^{-3}; for 3-RDM, both proposed methods outperform previous algorithms.","The sine-state QAE achieves near-optimal MSE $(\\pi/2^{q+1})^2 + O(2^{-3q})$ with $2q+1$ queries, and expectation-value estimation via QAE requires $O(1)/\\epsilon$ queries.","Method II's space complexity grows as $O(kN^{2k}\\log(N/\\epsilon))$, trading additional qubits for a reduced query count compared with Method I's $O(N^{2k})$ space."],"supporting_citations":[{"why":"Supplies the original QGE algorithm on which the multi-parameter phase encoding and inverse-QFT measurement are based.","marker":"[28]"},{"why":"Provides the analysis of Jordan's algorithm with a phase oracle, yielding the error bound used to convert QPE estimates into gradient estimates.","marker":"[29]"},{"why":"Supplies the matrix-series inequality and tomography framework used in the proof of the spectral-norm bound for amplified block encodings.","marker":"[30]"},{"why":"Represents the prior nearly optimal multiple-observable estimation algorithm whose $O(N^k)/\\epsilon$ cost is a baseline for the k-RDM comparison.","marker":"[31]"},{"why":"Introduces the adaptive QGE algorithm and its sample-complexity framework, which the paper generalizes and improves with Methods I and II.","marker":"[32]"},{"why":"Gives the original QAE algorithm and the Grover operator whose phase encodes the target amplitude; the sine-state analysis builds on this circuit.","marker":"[19]"},{"why":"Provides the fermionic classical shadow protocol with the shadow-norm bound that sets the $O(N^k)/\\epsilon^2$ sampling baseline for k-RDM estimation.","marker":"[15]"},{"why":"Establishes the sine-state near-optimal phase estimation result that the paper adapts to prove Heisenberg-limited QAE.","marker":"[36]"},{"why":"Gives QSVT and uniform singular value amplification, the polynomial approximation machinery used to build the probe-state circuits.","marker":"[53]"},{"why":"Provides optimal block-Hamiltonian simulation, which fixes the polynomial degree and query count in the probe-state preparation.","marker":"[49]"}],"fun_headline_variants":["Adaptive QGE hits Heisenberg limit for k-RDMs","Quadratic improvement for fermionic k-RDM estimation","Heisenberg-limited algorithms cut query cost for k-RDMs","Cosine probe and symmetry sectors reduce k-RDM queries","New QGE variants achieve optimal queries for k-RDMs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the paper's assumption, in the proofs of Lemmas 5 and 7, that the circuit $V^{(q)}$ which subtracts the running estimates $u_j$ from the probe phases is implemented with an error small enough to ignore relative to the other approximation errors; no concrete bound on $\\delta_V$ is derived, so the state-preparation error $1/12$ (or $E$) and all subsequent query-complexity theorems inherit this gap.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive QGE hits Heisenberg limit for k-RDMs","Quadratic improvement for fermionic k-RDM estimation","Heisenberg-limited algorithms cut query cost for k-RDMs","Cosine probe and symmetry sectors reduce k-RDM queries","New QGE variants achieve optimal queries for k-RDMs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000623,"raw_usage":{"total_tokens":2890,"prompt_tokens":954,"completion_tokens":1936,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":1853}},"tokens_in":570,"tokens_out":1936,"duration_ms":15027,"temperature":1.0,"reasoning_tokens":1853,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:35:51.535274+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To falsify the central claim, one would need to exhibit an implementation of the estimate-subtraction circuit $V^{(q)}$ for a concrete instance (for example, the FeMo-cofactor 2-RDM at ε = $10^{{-3}}$) and compute its approximation error $\\delta_V$; if $\\delta_V$ is not much smaller than $\\varepsilon''$ ($2^{{-14}}$ in Method I, $(\\delta(q))^2/26$ in Method II), the Euclidean-distance bound of $1/12$ (or $E$) fails, and with it the proofs of the query-complexity theorems. More directly, a numerical simulation that counts queries including $V^{(q)}$ and shows the root MSE exceeds ε would settle the claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the original QGE algorithm on which the multi-parameter phase encoding and inverse-QFT measurement are based."},{"cited_title":"Gilyén, S","cited_arxiv_id":null,"evidence_quote":"Provides the analysis of Jordan's algorithm with a phase oracle, yielding the error bound used to convert QPE estimates into gradient estimates."},{"cited_title":"van Apeldoorn, A","cited_arxiv_id":null,"evidence_quote":"Supplies the matrix-series inequality and tomography framework used in the proof of the spectral-norm bound for amplified block encodings."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents the prior nearly optimal multiple-observable estimation algorithm whose $O(N^k)/\\epsilon$ cost is a baseline for the k-RDM comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the adaptive QGE algorithm and its sample-complexity framework, which the paper generalizes and improves with Methods I and II."},{"cited_title":"Brassard, P","cited_arxiv_id":null,"evidence_quote":"Gives the original QAE algorithm and the Grover operator whose phase encodes the target amplitude; the sine-state analysis builds on this circuit."},{"cited_title":"Fermionic partial tomography via classical shadows","cited_arxiv_id":"2010.16094","evidence_quote":"Provides the fermionic classical shadow protocol with the shadow-norm bound that sets the $O(N^k)/\\epsilon^2$ sampling baseline for k-RDM estimation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the sine-state near-optimal phase estimation result that the paper adapts to prove Heisenberg-limited QAE."},{"cited_title":"Gilyén, Y","cited_arxiv_id":null,"evidence_quote":"Gives QSVT and uniform singular value amplification, the polynomial approximation machinery used to build the probe-state circuits."}],"review_version":1}