Pith. sign in

REVIEW 4 major objections 3 minor 2 cited by

Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation

T0 review · 4 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An adaptive symmetry-aware quantum scheme estimates all fermionic k-RDM elements with query cost ~N^{k/2}/ε at fixed particle number.

desk verdict 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. read the letter →

arxiv 2505.00698 v2 pith:WSERWYKE submitted 2025-05-01 quant-ph

Yuki Koizumi , Kaito Wada , Wataru Mizukami , Nobuyuki Yoshioka This is my paper · ORCID
classification quant-ph MSC 81P6868Q12 PACS 03.67.Ac03.67.Lx
keywords quantumamplitudeestimationgradientHeisenberglimitfermionick-RDMadaptivesignalprocessingsubspaceQSVTquerycomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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}}$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

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.

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 (4)
  1. [Section VB, Lemma 4 (Eqs. (117)-(118), proof near Eq. (129))] 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.
  2. [Section VB, proof of Lemma 5 (Eq. (144))] 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.
  3. [Section VB/VD, Lemmas 5 and 7, and Theorem 4] 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.
  4. [Section IIIA, sine-state near-optimality] 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.
minor comments (3)
  1. [Throughout] 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.
  2. [Section VIA, Table 2] 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.
  3. [Section VI, Algorithms 5 and 6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the claimed O~(N^{k/2})/ε costs follow from explicitly stated amplification, Hamiltonian-simulation, and sample-count bounds, not from fitted targets or from a self-cited prior result.

full rationale

The derivation chain is not circular. Algorithm 1/Theorem 1 supplies an adaptive MSE-accumulation argument; its proof follows Ref. [32], but that framework is used as a scaffold and does not itself assert the new resource claims. The new claims come from Lemma 4/Lemma 5 (symmetry-amplified probe state) and Lemma 6/Lemma 7 (parallel probe state), whose proofs use explicit concentration inequalities and explicit constants (v=0.1652 from the cosine state, delta'=2^-10, epsilon' = sqrt(delta')/(2^{p+q+2}sigma_Delta), etc.). The k-RDM bound in Lemma 11 is a combinatorial count of rank-one projections, independent of any fitted expectation value. Numerical query counts are evaluations of these stated formulas against external baselines (fermionic classical shadows, QAE), not predictions of fitted data. The only prominent gap, the unproved assumption in Lemma 5 that delta_V is 'sufficiently small', is an unquantified rigor assumption, not a circular reduction: no target MSE or query count is defined in terms of delta_V, and delta_V is not fitted from the quantities being predicted. Similarly, the flagged algebra in Lemma 4's Bernstein step is a soundness/correctness concern; even if the threshold is wrong, the claimed result would be unsupported, not equivalent to its input. Self-citations to Ref. [32] and to the companion paper [33] identify the prior adaptive-QGE framework and its PREPARE tricks; the improvements (cosine state, subspace QSVT, parallel amplification) are argued in the present text and checked numerically. No quoted step reduces by construction to a fit or to a self-citation chain.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central results depend on standard oracle and symmetry assumptions, plus one unproved smallness assumption about the correction circuit V^(q). No new physical entities are introduced. The chosen constants c, p, delta', and epsilon'' are numerical parameters that influence constant factors and the reported resource counts, but not the asymptotic scaling.

free parameters (4)
  • c = 1/(80(1+pi)^2)
    Confidence parameter in Algorithm 1 and Theorem 1, chosen to lower q_max to ceil(log2(1/(sqrt(40/11)epsilon))) and entering the numerical query counts; not data-fitted but a hand-picked constant affecting the constants in the results.
  • p = 3
    Grid precision parameter fixed to 3 based on numerical comparison of probe states in Section VA and Figure 5; the failure probability mu=0.011+1/12 and R(q)=4 log(M/delta(q)) in Theorem 2 depend on p=3.
  • delta' = 2^{-10} (Method I); (delta(q))^2/80 (Method II)
    Failure probability for the exceptional set F_Delta in Lemma 4 and Lemma 6; chosen small to make the Euclidean distance bound work. It is a tunable accuracy parameter.
  • epsilon'' = 2^{-14} (Method I); (delta(q))^2/26 (Method II)
    Hamiltonian simulation precision in Algorithms 5 and 6; set small to keep the total error below 1/12 or E. Not fitted to the target result.
assumptions (5)
  • domain assumption Oracular access to U_psi and U_psi^dagger and block-encodings B_j of observables with ||O_j|| <= 1.
    Problem 1 and Definition 1 set the oracle model; all algorithms count only queries to U_psi, so the entire framework rests on this assumption.
  • domain assumption The target state |psi> is exactly supported on the symmetry subspace Delta, i.e., Pi_Delta |psi> = |psi>, and observables are G-symmetric with the irreducible decomposition O_j = oplus_lambda 1_{C^{d_lambda}} otimes O_j^{(lambda)}.
    Theorem 2 and Lemma 5 use this to restrict subspace QSVT to Delta; leakage outside Delta breaks the estimator because the amplified block-encoding only approximates the observable on Delta.
  • ad hoc to paper The circuit V^(q), which subtracts running estimates u_j, is implemented with error delta_V sufficiently small relative to epsilon'' and delta'.
    Proof of Lemma 5 and Lemma 7 states 'we assume that delta_V is sufficiently small' with no derived bound; the Euclidean distance bound and the sample complexity depend on this unproved component.
  • standard math Standard QSVT and Hamiltonian simulation results (Lemma 14 and Lemma 15) hold for the constructed block encodings.
    Used in Lemma 5 and Lemma 7 to simulate e^{iHt}; these results are cited from Refs. [49], [53], and [56].
  • standard math The sine state chi_q can be prepared with O~(q) gates and the variant QFT^dagger_{G_p} is equivalent to the standard QFT up to local gates.
    Used in Lemmas 1 and 2 and in the QGE circuit; preparation efficiency is cited from Ref. [41].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation." pith.science (2026). https://pith.science/paper/WSERWYKE

@misc{pith2026250500698,
  author       = {Pith},
  title        = {Pith review of: Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WSERWYKE}},
  note         = {Machine review of arXiv:2505.00698}
}
abstract

In the accompanying paper of arXiv:2505.00697, we have presented a generalized scheme of adaptive quantum gradient estimation (QGE) algorithm, and further proposed two practical variants which not only achieve doubly quantum enhancement in query complexity regarding estimation precision and number of observables, but also enable minimal cost to estimate $k$-RDMs in fermionic systems among existing quantum algorithms. Here, we provide full descriptions on the algorithm, and provide theoretical guarantee for the estimation precision in terms of the root mean squared error. Furthermore, we analyze the performance of the quantum amplitude estimation algorithm, another variant of the Heisenberg-limited scaling algorithm, and show how the estimation error is minimized under the circuit structure that resembles the phase estimation algorithm. We finally describe the details for the numerical evaluation of the query complexity of the Heisenberg-limited algorithms and sampling-based methods to make a thorough comparison in the task of estimating fermionic $k$-RDMs.

Figures

Figures reproduced from arXiv: 2505.00698 by the authors.

Figure 1
Figure 1. Improved circuit construction of QAE algorithm with an initial state preparation unitary [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Standard circuit construction of QAE algorithm with an initial state preparation unitary [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The MSE in the amplitude estimation with (a) [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (5 more)
Figure 5
Figure 5. Figure 5: Performance of various (p = 3)-qubit probe states. The interval θ ∈ [0, 1] is discretized into 106 points. For clarity, we present the failure probability in the range θ ∈ [0, 0.5], as the plot over θ ∈ [0.5, 1] exhibits identical behavior due to periodicity. The probe…
Figure 6
Figure 6. Figure 6: Quantum circuit for the optimal Hamiltonian simulation for the Hamiltonian [PITH_FULL_IMAGE:figures/full_fig_p024_6.png]
Figure 7
Figure 7. Figure 7: The cancellation of Uψ and its inverse in the quantum circuit sequence shown in [PITH_FULL_IMAGE:figures/full_fig_p025_7.png]
Figure 8
Figure 8. Figure 8: The total query complexity in terms of state preparation unitary [PITH_FULL_IMAGE:figures/full_fig_p054_8.png]
Figure 9
Figure 9. Figure 9: The QSVT circuit UΦ transforms a block-encoding UA of A into a block-encoding of f(A), where f : [−1, 1] → [−1, 1] is a definite-parity polynomial of degree m. The phase angles {ϕi} can be classically computed [PITH_FULL_IMAGE:figures/full_fig_p055_9.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Near-Heisenberg-limited parallel amplitude estimation with logarithmic depth circuit

    quant-ph 2025-08 unverdicted novelty 7.0 of 10

    A tunable parallel amplitude estimation algorithm achieves near-Heisenberg query scaling and logarithmic depth via GHZ states and quantum signal processing, with a near-optimality proof using the parallel quantum adve...

  2. Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems

    quant-ph 2025-05 conditional novelty 7.0 of 10

    Symmetry-tailored and parallel-readout variants of adaptive quantum gradient estimation cut the state-preparation query count for fermionic k-RDM estimation, giving a quadratic speedup over prior QGE methods at fixed ...

Reference graph

Works this paper leans on

63 extracted references · 41 canonical work pages · cited by 2 Pith papers

  1. [32]

    K. Wada, N. Yamamoto, and N. Yoshioka, Heisenberg-limited adaptive gradient estimation for multiple observables, PRX Quantum 6, 020308 (2025)

    work page 2025

  2. [1]

    Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    S. Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    1996

  3. [2]

    Aspuru-Guzik, A

    A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Simulated quantum computation of molecular energies, Science 309, 1704 (2005)

    work page 2005

  4. [3]

    Biamonte, P

    J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature549, 195 (2017)

    2017

  5. [4]

    Knill, G

    E. Knill, G. Ortiz, and R. D. Somma, Optimal quantum measurements of expectation values of observables, Physical Review A—Atomic, Molecular, and Optical Physics75, 012328 (2007)

    work page 2007

  6. [5]

    Erhard, J

    A. Erhard, J. J. Wallman, L. Postler, M. Meth, R. Stricker, E. A. Martinez, P. Schindler, T. Monz, J. Emerson, and R. Blatt, Characterizing large-scale quantum computers via cycle benchmarking, Nature Communications10, 5347 (2019)

    2019

  7. [6]

    Eisert, D

    J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum certification and benchmarking, Nature Reviews Physics2, 382 (2020)

    2020

  8. [7]

    S. J. van Enk and C. W. J. Beenakker, MeasuringTrρn on single copies ofρ using random measurements, Physical Review Letters 108, 110503 (2012)

    work page 2012

Show all 63 references
  1. [8]

    Elben, B

    A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller, Rényi entropies from random quenches in atomic hubbard and spin models, Physical Review Letters120, 050406 (2018)

    2018

  2. [9]

    Elben, B

    A. Elben, B. Vermersch, C. F. Roos, and P. Zoller, Statistical correlations between locally randomized measurements: A toolbox for probing entanglement in many-body quantum states, Physical Review A99, 052323 (2019)

    2019

  3. [10]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Phys.16, 1050 (2020), arXiv:2002.08953 [quant-ph]

    2020 arXiv

  4. [11]

    Elben, S

    A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nature Reviews Physics5, 9 (2023)

    2023

  5. [12]

    Cotler and F

    J. Cotler and F. Wilczek, Quantum overlapping tomography, Physical review letters124, 100401 (2020)

    2020

  6. [13]

    Bonet-Monroig, R

    X. Bonet-Monroig, R. Babbush, and T. E. O’Brien, Nearly optimal measurement scheduling for partial tomography of quantum states, Physical Review X10, 031064 (2020)

    2020

  7. [14]

    García-Pérez, M

    G. García-Pérez, M. A. Rossi, B. Sokolov, F. Tacchino, P. K. Barkoutsos, G. Mazzola, I. Tavernelli, and S. Maniscalco, Learning to measure: Adaptive informationally complete generalized measurements for quantum algorithms, PRX Quan- tum 2, 040342 (2021)

    2021

  8. [15]

    A. Zhao, N. C. Rubin, and A. Miyake, Fermionic partial tomography via classical shadows, Phys. Rev. Lett.127, 110504 (2021), arXiv:2010.16094 [quant-ph]

    2021 arXiv

  9. [16]

    G. H. Low, Classical shadows of fermions with particle number symmetry, arXiv preprint arXiv:2208.08964 (2022)

    2022 arXiv

  10. [17]

    T. Gu, X. Yuan, and B. Wu, Efficient measurement schemes for bosonic systems, Quantum Science and Technology8, 045008 (2023)

    2023

  11. [18]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information-theoretic bounds on quantum advantage in machine learning, Physical Review Letters126, 190505 (2021). 44

    2021

  12. [19]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemporary Mathe- matics 305, 53 (2002)

    2002

  13. [20]

    Rall, Quantum algorithms for estimating physical quantities using block encodings, Physical Review A102, 022408 (2020)

    P. Rall, Quantum algorithms for estimating physical quantities using block encodings, Physical Review A102, 022408 (2020)

    2020

  14. [21]

    Montanaro, Quantum speedup of monte carlo methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences471, 20150301 (2015)

    A. Montanaro, Quantum speedup of monte carlo methods, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences471, 20150301 (2015)

    2015

  15. [22]

    Suzuki, S

    Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Amplitude estimation without phase estima- tion, Quantum Information Processing19, 75 (2020)

    2020

  16. [23]

    Nakaji, Faster amplitude estimation, arXiv preprint arXiv:2003.02417 (2020)

    K. Nakaji, Faster amplitude estimation, arXiv preprint arXiv:2003.02417 (2020)

    2020 arXiv

  17. [24]

    Grinko, J

    D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, Iterative quantum amplitude estimation, npj Quantum Information7, 52 (2021)

    2021

  18. [25]

    Y. Zhao, H. Wang, K. Xu, Y. Wang, J. Zhu, and F. Wang, Adaptive algorithm for quantum amplitude estimation, arXiv preprint arXiv:2206.08449 (2022)

    2022 arXiv

  19. [26]

    Rall and B

    P. Rall and B. Fuller, Amplitude estimation from quantum signal processing, Quantum7, 937 (2023)

    2023

  20. [27]

    Fukuzawa, C

    S. Fukuzawa, C. Ho, S. Irani, and J. Zion, Modified iterative quantum amplitude estimation is asymptotically optimal, in 2023 proceedings of the symposium on algorithm engineering and experiments (ALENEX) (SIAM, 2023) pp. 135–147

    2023

  21. [28]

    S. P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical review letters95, 050501 (2005)

    2005

  22. [29]

    Gilyén, S

    A. Gilyén, S. Arunachalam, and N. Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , 1425 (2019)

    2019

  23. [30]

    van Apeldoorn, A

    J. van Apeldoorn, A. Cornelissen, A. Gilyén, and G. Nannicini, Quantum tomography using state-preparation unitaries, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 1265 (2023)

    2023

  24. [31]

    W. J. Huggins, K. Wan, J. McClean, T. E. O’Brien, N. Wiebe, and R. Babbush, Nearly optimal quantum algorithm for estimating multiple expectation values, Physical Review Letters129, 240501 (2022)

    2022

  25. [33]

    Koizumi, K

    Y. Koizumi, K. Wada, W. Mizukami, and N. Yoshioka, Faster quantum algorithm for multiple observables estimation in fermionic problems, arXiv preprint (2025), arXiv:2505.00697 [quant-ph]

    2025 arXiv

  26. [34]

    B. L. Higgins, D. W. Berry, S. D. Bartlett, M. W. Mitchell, H. M. Wiseman, and G. J. Pryde, Demonstrating Heisenberg- limited unambiguous phase estimation without adaptive measurements, New Journal of Physics 11, 073023 (2009), arXiv:0809.3308 [quant-ph]

    2009 arXiv

  27. [35]

    D. W. Berry, H. M. Wiseman, and J. K. Breslin, Optimal input states and feedback for interferometric phase estimation, Phys. Rev. A63, 053804 (2001)

    2001

  28. [36]

    D. W. Berry, B. L. Higgins, S. D. Bartlett, M. W. Mitchell, G. J. Pryde, and H. M. Wiseman, How to perform the most accurate possible phase measurements, Physical Review A—Atomic, Molecular, and Optical Physics80, 052114 (2009)

    2009

  29. [37]

    Z. Ji, G. Wang, R. Duan, Y. Feng, and M. Ying, Parameter estimation of quantum channels, IEEE Transactions on Information Theory54, 5172 (2008)

    2008

  30. [38]

    Suzuki, S

    Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Amplitude estimation without phase estima- tion, Quantum Information Processing19, 75 (2020), arXiv:1904.10246 [quant-ph]

    2020 arXiv

  31. [39]

    G. Wang, D. E. Koh, P. D. Johnson, and Y. Cao, Minimizing estimation runtime on noisy quantum computers, PRX Quantum 2, 010346 (2021)

    2021

  32. [40]

    T. E. O’Brien, M. Streif, N. C. Rubin, R. Santagati, Y. Su, W. J. Huggins, J. J. Goings, N. Moll, E. Kyoseva, M. Degroote, C. S. Tautermann, J. Lee, D. W. Berry, N. Wiebe, and R. Babbush, Efficient quantum computation of molecular forces and other energy gradients, Phys. Rev. ...

    2022

  33. [41]

    Babbush, C

    R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear t complexity, Physical Review X8, 041015 (2018)

    2018

  34. [42]

    M. A. Nielsen and I. L. Chuang,Quantum computation and quantum information (Cambridge university press, 2010)

    2010

  35. [43]

    [32] provides anϵ-precise block-encoding of 2M π2⌈log2M⌉ , but we ignore this normalization factor as it can be adjusted to unity via uniform singular value amplification

    More precisely, Ref. [32] provides anϵ-precise block-encoding of 2M π2⌈log2M⌉ , but we ignore this normalization factor as it can be adjusted to unity via uniform singular value amplification

  36. [44]

    Rendon, T

    G. Rendon, T. Izubuchi, and Y. Kikuchi, Effects of cosine tapering window on quantum phase estimation, Physical Review D 106, 034503 (2022)

    2022

  37. [45]

    Greenaway, W

    S. Greenaway, W. Pol, and S. Sim, A case study against qsvt: assessment of quantum phase estimation improved by signal processing techniques, arXiv preprint arXiv:2404.01396 (2024)

    2024 arXiv

  38. [46]

    Patel, S

    D. Patel, S. J. S. Tan, Y. Subasi, and A. T. Sornborger, Optimal coherent quantum phase estimation via tapering, arXiv preprint arXiv:2403.18927 (2024)

    2024 arXiv

  39. [47]

    O’Brien and C

    O. O’Brien and C. Sünderhauf, Quantum state preparation via piecewise qsvt, arXiv preprint arXiv:2409.07332 (2024)

    2024 arXiv

  40. [48]

    Mitsuhashi, R

    Y. Mitsuhashi, R. Suzuki, T. Soejima, and N. Yoshioka, Unitary designs of symmetric local random circuits, arXiv preprint arXiv:2408.13472 (2024)

    2024 arXiv

  41. [49]

    G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum3, 163 (2019)

    2019

  42. [50]

    K. Wan, W. J. Huggins, J. Lee, and R. Babbush, Matchgate shadows for fermionic quantum simulation, Communications in Mathematical Physics404, 629 (2023)

    2023

  43. [51]

    Babbush, W

    R. Babbush, W. J. Huggins, D. W. Berry, S. F. Ung, A. Zhao, D. R. Reichman, H. Neven, A. D. Baczewski, and J. Lee, Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods, Nature Communications 14, 4058 (2023). 45

    2023

  44. [52]

    O’Gorman, Fermionic tomography and learning, arXiv preprint arXiv:2207.14787 (2022)

    B. O’Gorman, Fermionic tomography and learning, arXiv preprint arXiv:2207.14787 (2022)

    2022 arXiv

  45. [53]

    Gilyén, Y

    A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , 193 (2019)

    2019

  46. [54]

    Kimmel, G

    S. Kimmel, G. H. Low, and T. J. Yoder, Robust calibration of a universal single-qubit gate set via robust phase estimation, Phys. Rev. A92, 062315 (2015)

    2015

  47. [55]

    Y.AtiaandD.Aharonov,Fast-forwardingofhamiltoniansandexponentiallyprecisemeasurements,Naturecommunications 8, 1572 (2017)

    2017

  48. [56]

    G. H. Low and I. L. Chuang, Hamiltonian simulation by uniform spectral amplification, arXiv preprint arXiv:1707.05391 (2017)

    2017 arXiv

  49. [57]

    Zlokapa and R

    A. Zlokapa and R. D. Somma, Hamiltonian simulation for low-energy states with optimal time dependence, arXiv preprint arXiv:2404.03644 (2024)

    2024 arXiv

  50. [58]

    J. A. Troppet al., An introduction to matrix concentration inequalities, Foundations and Trends® in Machine Learning 8, 1 (2015). A. Quantum arithmetic techniques In this section, we state key results related to QSVT. By leveraging these QSVT techniques, we can explicitly cons...

    2015

  51. [59]

    [58] and Theorem 35 in Ref

    The proof of Eq.(128) In this section, we show a detailed proof of the Bernstein inequality for a sum of Hermitian operators with inde- pendent, symmetrically distributed random variable coefficients based on Theorem 6.6.1 in Ref. [58] and Theorem 35 in Ref. [30]. Here, ford×d...

  52. [60]

    Notably, our target bound involves the cumulative distribution function (CDF), which is generally intractable to compute analytically

    Tighter probability bound for median estimate In this section, we present a tighter probability bound for the median of independent samples, improving upon Hoeffding’s inequality. Notably, our target bound involves the cumulative distribution function (CDF), which is generally...

  53. [61]

    RX r=1 Zr≥ R 2 # (D19) = 1− Pr

    Then, the probability that the median deviates from the true value exceedsε is bounded as Pr h k(med)−k∗ >ε i ≤ 1−F R 2 − 1;µ,R , (D17) wherek(med) denotes the median of{k(r)}R r=1, andF (n;µ,R ) is the cumulative distribution function of the binomial distribution with success...

  54. [62]

    Explict implementation of block-encoding for fermionick-RDM estimation In this section, we examine the explicit implementation of block-encodings for operators used to evaluate fermionic k-RDMs. In order to estimate the value of fermionick-RDM elements with QAE algorithm and o...

  55. [63]

    wWVfoWEYqDAAFZX/N2qiMIXlAe0=

    The evaluation of Eq.(227) Lemma 21. For integersk,η, if 0≤k≤η and η +k≤N holds, then, kX m=0 N k N−k k−m k m · N− (2k−m) η−k / N η = η k N−η +k k (D39) Proof. Firstly we rewrite the LHS of the target equation, kX m=0 N k N−k k−m k m · N− (2k−m) η−k / N η = N k N η kX m=0 N−k ...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.