arxiv: 2603.05475 · v2 · submitted 2026-03-05 · 🪐 quant-ph

Recognition: 2 theorem links

· Lean Theorem

Low-depth amplitude estimation via statistical eigengap estimation

Po-Wei Huang , B\'alint Koczor

Authors on Pith no claims yet

Pith reviewed 2026-05-15 15:47 UTC · model grok-4.3

classification 🪐 quant-ph

keywords amplitude estimationamplitude amplificationeigengap estimationlow-depth quantum circuitsHeisenberg limitGrover operatorquantum algorithmsstatistical estimation

0 comments

The pith

Amplitude estimation reduces to estimating the energy gap of an effective Hamiltonian generated by amplitude amplification.

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

The paper shows that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian whose discrete-time evolution is generated by amplitude amplification. This connection lets statistical eigengap estimation methods from ground-state energy estimation be imported to create new amplitude estimation algorithms. The resulting methods work in both Heisenberg-limited and low-depth circuit regimes, achieving near-optimal query-depth tradeoffs up to polylog factors in the low-depth case along with provable guarantees and better empirical performance than prior low-depth approaches. The protocol needs no ancilla qubits and only standard Grover reflections, making it practical for early fault-tolerant quantum devices.

Core claim

By identifying amplitude estimation with energy gap estimation on an effective Hamiltonian generated by the Grover iterate, statistical phase estimation techniques can be applied to yield amplitude estimation protocols that achieve optimal query-depth tradeoffs up to polylogarithmic factors in low-depth settings while maintaining Heisenberg-limited performance with simplified classical post-processing.

What carries the argument

The effective Hamiltonian constructed from the amplitude amplification operator, to which statistical eigengap estimation is applied.

Load-bearing premise

Statistical eigengap estimation techniques transfer directly to the effective Hamiltonian from amplitude amplification without introducing unaccounted overhead, bias, or loss of optimality guarantees.

What would settle it

A numerical simulation or small-scale quantum experiment that shows the query complexity or error scaling deviates from the predicted optimal tradeoffs when the statistical eigengap method is applied to the amplitude amplification operator.

Figures

Figures reproduced from arXiv: 2603.05475 by B\'alint Koczor, Po-Wei Huang.

**Figure 2.** Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 5.** Figure 5: shows such discussions when plotted. As a consequence, the range of a that can be estimated is limited by the width of the Gaussian peak, as parameterized by T and limited by the maximum circuit depth M = ⌊σT⌋. This limitation of the inability to estimate amplitudes a close to 0 or 1 is not unique to our algorithm, but has also been shown to exist in prior work [8]. 2. Proofs for GLSAE We now discuss the … view at source ↗

**Figure 6.** Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗

**Figure 7.** Figure 7: FIG. 7 [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗

**Figure 8.** Figure 8: FIG. 8 [PITH_FULL_IMAGE:figures/full_fig_p027_8.png] view at source ↗

**Figure 9.** Figure 9: FIG. 9 [PITH_FULL_IMAGE:figures/full_fig_p027_9.png] view at source ↗

**Figure 10.** Figure 10: FIG. 10 [PITH_FULL_IMAGE:figures/full_fig_p028_10.png] view at source ↗

**Figure 11.** Figure 11: FIG. 11 [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗

read the original abstract

Amplitude estimation, in its original form, is formulated as phase estimation upon the Grover iterate. Subsequent improvements to the algorithm have eliminated the need for phase estimation and introduced low-depth variants that trade speedups for lower circuit depth. We make the key observation that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian, whereby discrete-time evolution is generated by amplitude amplification. This enables us to develop an amplitude estimation algorithm for both Heisenberg-limited and low-depth circuit regimes, inspired by statistical phase estimation techniques developed for early fault-tolerant ground-state energy estimation. In the Heisenberg-limited regime, our approach achieves performance comparable to state-of-the-art methods while using simplified classical post-processing. In the low-depth regime, it obtains optimal query--depth tradeoffs up to polylogarithmic factors, with provable guarantees and improved empirical performance over prior approaches. The resulting protocol is ancilla-free and requires only standard Grover reflections. Due to its flexibility, generality, and robustness, we expect our approach to be a key enabler for a broad range of early fault-tolerant applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper maps amplitude estimation to eigengap estimation on an effective Hamiltonian from the Grover iterate, letting them import statistical phase estimation methods for both Heisenberg and low-depth regimes.

read the letter

The central move is treating amplitude estimation as energy gap estimation for an effective Hamiltonian whose discrete evolution is generated by amplitude amplification. This lets them adapt statistical techniques from ground-state energy estimation to produce ancilla-free protocols that use only standard Grover reflections. In the Heisenberg-limited case the post-processing is simpler than standard methods while matching performance. In the low-depth regime they report optimal query-depth tradeoffs up to polylog factors, provable guarantees, and better empirical results than prior low-depth approaches. The flexibility for early fault-tolerant tasks like Monte Carlo or sampling is a clear practical plus. The mapping itself is the genuinely new piece; the rest builds directly on existing statistical phase estimation work. The soft spot is whether the transfer from continuous Hamiltonian methods to the discrete unitary case is exact. The stress-test concern about possible spectrum mismatch or sampling bias is worth checking in the derivations, because any unaccounted overhead would weaken the optimality claims. The abstract asserts the guarantees hold, but the full error analysis and how they handle the discrete-to-effective-H step need to be verified before the low-depth advantages can be taken as settled. Empirical comparisons look improved, though details on parameter choices would help assess robustness. This is for quantum algorithm researchers focused on resource tradeoffs in the early fault-tolerant regime. A reader working on sampling or optimization primitives would get concrete value from the protocol if the guarantees check out. It deserves peer review because the reframing is specific, the claims are testable, and the potential resource savings are worth referee scrutiny even if revisions are needed on the bias analysis.

Referee Report

1 major / 2 minor

Summary. The paper claims that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian generated by the amplitude amplification (Grover) operator. This equivalence allows transferring statistical eigengap estimation techniques from ground-state energy estimation to develop new algorithms for both the Heisenberg-limited regime (with simplified classical post-processing) and the low-depth regime (achieving optimal query-depth tradeoffs up to polylog factors, with provable guarantees and improved empirical performance). The protocol is ancilla-free and uses only standard Grover reflections.

Significance. If the central equivalence and transfer of estimators hold with the claimed bounds, the work is significant: it provides a flexible, robust framework that unifies amplitude estimation with early fault-tolerant ground-state methods, simplifies post-processing, and delivers practical low-depth protocols that could enable a range of near-term quantum applications beyond current approaches.

major comments (1)

[§3] §3 (Mapping to effective Hamiltonian): The discrete-time Grover iterate is mapped to an effective Hamiltonian for eigengap estimation. The manuscript must explicitly show that the spectrum and sampling distribution of this effective operator preserve the unbiasedness and variance bounds of the statistical estimators from the ground-state literature; any implicit continuous approximation or series truncation could introduce bias or extra polylog factors that would undermine the optimality claim in the low-depth regime.

minor comments (2)

[Abstract] Abstract: the phrase 'optimal query–depth tradeoffs up to polylogarithmic factors' should be accompanied by a brief statement of the precise polylog degree and the constants hidden in the O-notation to allow immediate comparison with prior low-depth amplitude estimation results.
[Figure 2] Figure 2 (empirical comparison): the caption should clarify the exact circuit depth metric used (e.g., number of Grover reflections per sample) and whether the plotted error bars reflect only statistical variance or also include any post-selection overhead.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending minor revision. We address the single major comment below.

read point-by-point responses

Referee: [§3] §3 (Mapping to effective Hamiltonian): The discrete-time Grover iterate is mapped to an effective Hamiltonian for eigengap estimation. The manuscript must explicitly show that the spectrum and sampling distribution of this effective operator preserve the unbiasedness and variance bounds of the statistical estimators from the ground-state literature; any implicit continuous approximation or series truncation could introduce bias or extra polylog factors that would undermine the optimality claim in the low-depth regime.

Authors: We thank the referee for this constructive comment. The mapping in §3 is exact and does not rely on any continuous-time approximation or series truncation. The Grover iterate G is a unitary whose eigenvalues are precisely e^{±iθ} with θ = 2 arcsin(√a) (a the target amplitude). We define the effective Hamiltonian H_eff via its eigenvalues θ ∈ [0, π], so that powers G^k correspond exactly to discrete-time evolution under H_eff. The statistical eigengap estimators are applied directly to the sequence of measurement outcomes obtained from these discrete applications of G (via standard reflections), without any intermediate approximation. Consequently the spectrum is exact and the induced sampling distribution matches the assumptions of the ground-state estimators exactly, preserving unbiasedness and the stated variance bounds with no additional bias or polylog factors. To make this fully explicit we will add a short derivation (new subsection in §3 or dedicated appendix paragraph) that verifies the eigenvalue correspondence and the exact matching of the probability distribution to the conditions required by the estimators. This addition will confirm that the low-depth optimality claims remain rigorous. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's key step is the observation that amplitude estimation equates to eigengap estimation of an effective Hamiltonian whose evolution is generated by the Grover iterate; this mapping is used to transfer statistical phase estimation methods from ground-state energy estimation literature. No quoted equations or claims reduce a prediction to a fitted parameter by construction, nor does any load-bearing premise collapse to a self-citation chain or self-definitional loop. The claimed optimality guarantees and query-depth tradeoffs are asserted via provable properties of the transferred techniques rather than by renaming or re-fitting the inputs. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the equivalence between amplitude estimation and eigengap estimation plus the transferability of statistical phase estimation techniques; no free parameters, new entities, or non-standard axioms are explicitly introduced in the abstract.

axioms (1)

standard math Standard quantum circuit model with Grover reflections and discrete-time evolution generated by amplitude amplification.
Invoked when defining the effective Hamiltonian whose gap is estimated.

pith-pipeline@v0.9.0 · 5481 in / 1358 out tokens · 44184 ms · 2026-05-15T15:47:21.852437+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We make the key observation that amplitude estimation is equivalent to estimating the energy gap of an effective Hamiltonian, whereby discrete-time evolution is generated by amplitude amplification... Q = −(I−2|ψ⟩⟨ψ|)(I−2P) ... H_eff = −2λ Y_ψ + π(I−P−|ψ_b⟩⟨ψ_b|)... eigenvalues ±2λ = ±2 arcsin(√a)
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the expected value ... yields ... cos(2λ m) ... loss function ˜L(θ) = 1/N Σ (Z_m − cos(2θ m))^2 ... Gaussian-filtered ... GLSAE/GDMAE

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

Universal Analog Quantum Simulation
quant-ph 2026-05 unverdicted novelty 5.0

UAQS turns fixed analog quantum simulators into programmable ones by engineering target many-body dynamics with optimized continuous control fields instead of discrete gates.

Reference graph

Works this paper leans on

92 extracted references · 92 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

Knill, G

E. Knill, G. Ortiz, and R. D. Somma, Optimal quantum measurements of expectation values of observables, Phys. Rev. A75, 012328 (2007)

work page 2007
[2]

Rebentrost, B

P. Rebentrost, B. Gupt, and T. R. Bromley, Quantum computational finance: Monte Carlo pricing of financial derivatives, Phys. Rev. A98, 022321 (2018)

work page 2018
[3]

Stamatopoulos, D

N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner, Option pricing using quantum computers, Quantum4, 291 (2020)

work page 2020
[4]

D. J. Egger, R. Garcia Gutierrez, J. C. Mestre, and S. Woerner, Credit risk analysis using quantum computers, IEEE Trans. Comput.70, 2136 (2021)

work page 2021
[5]

Woerner and D

S. Woerner and D. J. Egger, Quantum risk analysis, npj Quantum Inf.5(2019)

work page 2019
[6]

Chakrabarti, R

S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stam- atopoulos, S. Woerner, and W. J. Zeng, A threshold for quantum advantage in derivative pricing, Quantum5, 463 (2021)

work page 2021
[7]

Kassal, S

I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics, Proc. Natl. Acad. Sci. U.S.A.105, 18681–18686 (2008)

work page 2008
[8]

T. E. O’Brien, M. Streif, N. C. Rubin, R. Santagati, Y. Su, W. J. Huggins, J. J. Goings, N. Moll, E. Kyoseva, M. De- groote, C. S. Tautermann, J. Lee, D. W. Berry, N. Wiebe, and R. Babbush, Efficient quantum computation of molec- ular forces and other energy gradients, Phys. Rev. Res.4, 043210 (2022)

work page 2022
[9]

Huang, G

P.-W. Huang, G. Boyd, G.-L. R. Anselmetti, M. Deg- roote, N. Moll, R. Santagati, M. Streif, B. Ries, D. Marti- Dafcik, H. Jnane, S. Simon, N. Wiebe, T. R. Bromley, and B. Koczor, Fullqubit alchemist: Quantum algorithm for al- chemical free energy calculations (2025), arXiv:2508.16719 [quant-ph]

work page arXiv 2025
[10]

Quantum algorithms for zero-sum games

J. van Apeldoorn and A. Gily´ en, Quantum algorithms for zero-sum games (2019), arXiv:1904.03180 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2019
[11]

Huang and P

P.-W. Huang and P. Rebentrost, Quantum algorithm for large-scale market equilibrium computation, inAdvances in Neural Information Processing Systems, Vol. 37, edited by A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Pa- quet, J. Tomczak, and C. Zhang (Curran Associates, Inc.,

work page
[12]

Wiebe, A

N. Wiebe, A. Kapoor, and K. M. Svore, Quantum al- gorithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Inf. Comput.15, 316–356 (2015)

work page 2015
[13]

Wiebe, A

N. Wiebe, A. Kapoor, and K. M. Svore, Quantum deep learning, Quantum Inf. Comput.16, 541–587 (2016)

work page 2016
[14]

Kerenidis, J

I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, q-means: A quantum algorithm for unsupervised machine learning, inAdvances in Neural Information Processing Systems, Vol. 32, edited by H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch´ e-Buc, E. Fox, and R. Garnett (Curran Associates, Inc., 2019)

work page 2019
[15]

Kerenidis, J

I. Kerenidis, J. Landman, and A. Prakash, Quantum algorithms for deep convolutional neural networks, in International Conference on Learning Representations (2020)

work page 2020
[16]

Kerenidis and A

I. Kerenidis and A. Prakash, Quantum gradient descent for linear systems and least squares, Phys. Rev. A101, 022316 (2020)

work page 2020
[17]

Kerenidis and A

I. Kerenidis and A. Prakash, A quantum interior point method for LPs and SDPs, ACM Trans. Quantum Com- put.1(2020)

work page 2020
[18]

van Apeldoorn, A

J. van Apeldoorn, A. Gily´ en, S. Gribling, and R. de Wolf, Quantum SDP-solvers: Better upper and lower bounds, Quantum4, 230 (2020)

work page 2020
[19]

Sidford and C

A. Sidford and C. Zhang, Quantum speedups for stochas- tic optimization, inAdvances in Neural Information Pro- cessing Systems, Vol. 36, edited by A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Cur- ran Associates, Inc., 2023) pp. 35300–35330

work page 2023
[20]

Pillai, Y

S. Pillai, Y. Bar-Ness, and F. Haber, A new approach to array geometry for improved spatial spectrum estimation, Proc. IEEE73, 1522 (1985)

work page 1985
[21]

Roy and T

R. Roy and T. Kailath, ESPRIT-estimation of signal parameters via rotational invariance techniques, IEEE Trans. Acoust. Speech Signal Process.37, 984 (1989)

work page 1989
[22]

Liu and P

C.-L. Liu and P. P. Vaidyanathan, Remarks on the spatial smoothing step in coarray MUSIC, IEEE Signal Process. Lett.22, 1438 (2015)

work page 2015
[23]

E. T. Campbell, Early fault-tolerant simulations of the Hubbard model, Quantum Sci. Technol.7, 015007 (2021)

work page 2021
[24]

Katabarwa, K

A. Katabarwa, K. Gratsea, A. Caesura, and P. D. Johnson, Early fault-tolerant quantum computing, PRX Quantum 5, 020101 (2024)

work page 2024
[25]

Giurgica-Tiron, S

T. Giurgica-Tiron, S. Johri, I. Kerenidis, J. Nguyen, N. Pisenti, A. Prakash, K. Sosnova, K. Wright, and W. Zeng, Low-depth amplitude estimation on a trapped- ion quantum computer, Phys. Rev. Res.4, 033034 (2022)

work page 2022
[26]

van Apeldoorn, A

J. van Apeldoorn, A. Cornelissen, A. Gily´ en, and G. Nan- nicini, Quantum tomography using state-preparation uni- taries, inProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(Society for Industrial and Applied Mathematics, 2023) pp. 1265– 1318

work page 2023
[27]

Cornelissen and Y

A. Cornelissen and Y. Hamoudi, A sublinear-time quan- tum algorithm for approximating partition functions, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(Society for Industrial and Applied Mathematics, 2023) pp. 1245–1264

work page 2023
[28]

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

K. Oshio, K. Wada, and N. Yamamoto, Near-Heisenberg- limited parallel amplitude estimation with logarithmic depth circuit (2025), arXiv:2508.06121 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2025
[29]

J. M. Martyn, Z. M. Rossi, K. Z. Cheng, Y. Liu, and I. L. Chuang, Parallel quantum signal processing via polyno- mial factorization, Quantum9, 1834 (2025)

work page 2025
[30]

J. S. Nelson and A. D. Baczewski, Assessment of quan- tum phase estimation protocols for early fault-tolerant quantum computers, Phys. Rev. A110, 042420 (2024)

work page 2024
[31]

O. Kiss, U. Azad, B. Requena, A. Roggero, D. Wakeham, and J. M. Arrazola, Early fault-tolerant quantum algo- rithms in practice: Application to ground-state energy estimation, Quantum9, 1682 (2025)

work page 2025
[32]

B. L. Higgins, D. W. Berry, S. D. Bartlett, M. W. Mitchell, H. M. Wiseman, and G. J. Pryde, Demonstrat- ing Heisenberg-limited unambiguous phase estimation without adaptive measurements, New J. Phys.11, 073023 (2009)

work page 2009
[33]

Kimmel, G

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

work page 2015
[34]

Belliardo and V

F. Belliardo and V. Giovannetti, Achieving Heisenberg scaling with maximally entangled states: An analytic upper bound for the attainable root-mean-square error, Phys. Rev. A102, 042613 (2020)

work page 2020
[35]

A. E. Russo, K. M. Rudinger, B. C. A. Morrison, and A. D. Baczewski, Evaluating energy differences on a quantum 8 computer with robust phase estimation, Phys. Rev. Lett. 126, 210501 (2021)

work page 2021
[36]

Y. Dong, L. Lin, and Y. Tong, Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of uni- tary matrices, PRX Quantum3, 040305 (2022)

work page 2022
[37]

G. Wang, D. S. Fran¸ ca, G. Rendon, and P. D. Johnson, Efficient ground-state-energy estimation and certification on early fault-tolerant quantum computers, Phys. Rev. A 111, 012426 (2025)

work page 2025
[38]

R. D. Somma, Quantum eigenvalue estimation via time series analysis, New J. Phys.21, 123025 (2019)

work page 2019
[39]

Dutkiewicz, B

A. Dutkiewicz, B. M. Terhal, and T. E. O’Brien, Heisenberg-limited quantum phase estimation of multi- ple eigenvalues with few control qubits, Quantum6, 830 (2022)

work page 2022
[40]

Hua and T

Y. Hua and T. Sarkar, Matrix pencil method for esti- mating parameters of exponentially damped/undamped sinusoids in noise, IEEE Trans. Acoust. Speech Signal Process.38, 814 (1990)

work page 1990
[41]

Sarkar and O

T. Sarkar and O. Pereira, Using the matrix pencil method to estimate the parameters of a sum of complex exponen- tials, IEEE Antennas Propag. Mag.37, 48 (1995)

work page 1995
[42]

M. E. Stroeks, J. Helsen, and B. M. Terhal, Spectral estimation for Hamiltonians: a comparison between clas- sical imaginary-time evolution and quantum real-time evolution, New J. Phys.24, 103024 (2022)

work page 2022
[43]

H. Li, H. Ni, and L. Ying, Adaptive low-depth quantum algorithms for robust multiple-phase estimation, Phys. Rev. A108, 062408 (2023)

work page 2023
[44]

Z. Ding, E. N. Epperly, L. Lin, and R. Zhang, The ES- PRIT algorithm under high noise: Optimal error scaling and noisy super-resolution, in2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) (2024) pp. 2344–2366

work page 2024
[45]

C. Yi, C. Zhou, and J. Takahashi, Quantum phase esti- mation by compressed sensing, Quantum8, 1579 (2024)

work page 2024
[46]

Castaldo and S

D. Castaldo and S. Corni, Heisenberg limited multiple eigenvalue estimation via off-the-grid compressed sensing (2025), arXiv:2507.12438 [quant-ph]

work page arXiv 2025
[47]

E. J. Candes and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory52, 5406 (2006)

work page 2006
[48]

E. J. Candes, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incom- plete frequency information, IEEE Trans. Inf. Theory52, 489 (2006)

work page 2006
[49]

Y. Pati, R. Rezaiifar, and P. Krishnaprasad, Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, inProceedings of 27th Asilomar Conference on Signals, Systems and Computers(1993) pp. 40–44 vol.1

work page 1993
[50]

Zintchenko and N

I. Zintchenko and N. Wiebe, Randomized gap and ampli- tude estimation, Phys. Rev. A93, 062306 (2016)

work page 2016
[51]

Y. Yang, A. Christianen, M. C. Ba˜ nuls, D. S. Wild, and J. I. Cirac, Phase-sensitive quantum measurement with- out controlled operations, Phys. Rev. Lett.132, 220601 (2024)

work page 2024
[52]

H. H. S. Chan, R. Meister, M. L. Goh, and B. Koczor, Al- gorithmic shadow spectroscopy, PRX Quantum6, 010352 (2025)

work page 2025
[53]

Y. Yang, Y. Li, X. Xu, and X. Yuan, Resource-efficient quantum-classical hybrid algorithm for energy gap evalu- ation, Phys. Rev. A109, 052416 (2024)

work page 2024
[54]

Clinton, T

L. Clinton, T. S. Cubitt, R. Garcia-Patron, A. Montanaro, S. Stanisic, and M. Stroeks, Quantum phase estimation without controlled unitaries, PRX Quantum (2026)

work page 2026
[55]

Nesterov,Introductory Lectures on Convex Optimiza- tion: A Basic Course, Applied Optimization (Springer New York, NY, 2004)

Y. Nesterov,Introductory Lectures on Convex Optimiza- tion: A Basic Course, Applied Optimization (Springer New York, NY, 2004)

work page 2004
[56]

Giovannetti, S

V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Phys. Rev. Lett.96, 010401 (2006)

work page 2006
[57]

D. Wang, O. Higgott, and S. Brierley, Accelerated varia- tional quantum eigensolver, Phys. Rev. Lett.122, 140504 (2019)

work page 2019
[58]

Tong, A tight query complexity lower bound for phase estimation under circuit depth constraint (2021)

Y. Tong, A tight query complexity lower bound for phase estimation under circuit depth constraint (2021)

work page 2021
[59]

Z. Ding, Y. Dong, Y. Tong, and L. Lin, Robust ground- state energy estimation under depolarizing noise (2024), arXiv:2307.11257 [quant-ph]

work page arXiv 2024
[60]

Tibshirani, Regression shrinkage and selection via the Lasso, J

R. Tibshirani, Regression shrinkage and selection via the Lasso, J. R. Stat. Soc.: B (Methodol.)58, 267–288 (1996)

work page 1996
[61]

Low-depth amplitude estimation via statistical eigengap estimation

N. Derevianko, G. Plonka, and R. Razavi, ESPRIT versus ESPIRA for reconstruction of short cosine sums and its application, Numer. Algorithms92, 437–470 (2022). 9 Appendices for “Low-depth amplitude estimation via statistical eigengap estimation” CONTENTS A. Related work 9

work page 2022
[62]

Amplitude estimation 9

work page
[63]

An eigengap-based formulation of amplitude estimation 10

Phase estimation 10 B. An eigengap-based formulation of amplitude estimation 10

work page
[64]

Proof for amplitude amplification as discrete-time evolution 11

work page
[65]

Analytical properties of the periodic Gaussian 12

Proof for amplitude estimation as eigengap estimation 11 C. Analytical properties of the periodic Gaussian 12

work page
[66]

Local convexity of the periodic Gaussian 13

work page
[67]

Smoothness of the periodic Gaussian 13

work page
[68]

Further details on GLSAE 16

Strongly concave areas of the periodic Gaussian 15 D. Further details on GLSAE 16

work page
[69]

Algorithm and discussions for GLSAE 16

work page
[70]

Truncation and sampling errors of the loss function 19 b

Proofs for GLSAE 18 a. Truncation and sampling errors of the loss function 19 b. Main proof 21 E. Further details on GDMAE 22

work page
[71]

Algorithm and discussions for GDMAE 22

work page
[72]

Construction and properties of the alternating-sign periodic Gaussian 24 b

Proofs for GDMAE 24 a. Construction and properties of the alternating-sign periodic Gaussian 24 b. Truncation and sampling errors of the magnitude function 25 c. Main proof 26 F. Implementation details for numerics 27

work page
[73]

Heisenberg-limited amplitude estimation 27

work page
[74]

Low-depth amplitude estimation 29 Appendix A: Related work We now provide a summary of advancements in ampli- tude estimation and phase estimation in recent years

work page
[75]

low- depth

Amplitude estimation Amplitude estimation [1] is a staple in designing quan- tum algorithms with Grover-type speedups [ 3], due to its formulation as a quadratic speedup over classical Monte Carlo algorithms [36]. Since its introduction, amplitude estimation has been used to provide quantum algorithms for various applications such as finance [ 39–43], qua...

work page
[76]

jumps” in the continuity as eigenvalues of the evolved Hamilto- nian. Further work has been extended on what is now known as “statistical phase estimation

Phase estimation While efforts have been made in amplitude estimation to remove phase estimation as a subroutine, phase esti- mation itself has been vastly simplified to versions that only require one ancilla qubit. These versions utilize the Hadamard test [2, 14] instead of the full circuit including QFT as an early fault-tolerant alternative [ 67, 68]. ...

work page
[77]

[21] with a search method similar to orthogonal pursuit matching [86]

were able to provide low-depth algorithms for the multiple eigenvalue estimation problem, which was later improved by Dinget al. [21] with a search method similar to orthogonal pursuit matching [86]. Lastly, eigengap estimation and ancilla-free phase es- timation algorithms that discard the use of controlled unitaries and the ancilla qubit to have been ex...

work page
[78]

Proof for amplitude amplification as discrete-time evolution As mentioned in the main text, amplitude amplification can be written as a discrete-time evolution operator under some effective HamiltonianH eff such that fort∈N, Qt = −(I−2|ψ⟩⟨ψ|)(I−2P) t =e −itHeff .(B.1) The following proposition from the main text and proof obtainsH eff and its eigenvalues....

work page
[79]

Proof for amplitude estimation as eigengap estimation Given the construction of amplitude amplification as a discrete-time evolution operator, where the eigenvalues of the effective Hamiltonian in the nontrivial subspace Hψ being ±Eeff = ±2λ, the eigengap in this subspace is thus ∆eff = Eeff − (−Eeff) = 4λ. This can be extracted by eigengap estimation tec...

work page
[80]

Due to periodicity, results that specify a range are appli- cable with a periodicity of 2 π

Local convexity of the periodic Gaussian We now provide some results on the convexity and smoothness of Φ T for the ease of proof in later sections. Due to periodicity, results that specify a range are appli- cable with a periodicity of 2 π. For example, when we say convexity holds for and interval [ 1 T , 2π− 1 T ], the results also hold for [2 jπ + 1 T ...

work page

Showing first 80 references.