Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.24434

Nearly Optimal Amplitude Estimation at any Depth

Jona Erle, Bálint Koczor

quant-phSubmitted Aug 25, 2026• Announced Aug 26, 2026• 0 citations
arXivHTMLPDF

Abstract

We develop a class of amplitude estimation algorithms with tunable circuit depth $M$ and circuit repetitions $N$, requiring neither ancilla qubits nor controlled Grover operations. For additive error $ε$ in the Grover angle, they attain the nearly optimal query-depth tradeoff $M^2N\in\widetilde{O}(ε^{-2})$ uniformly over $λ\in[0,π/2]$, spanning the full range from classical sampling at $M=1$ to the Heisenberg limit at $M=Θ(ε^{-1})$. While prior depth-tunable work establishes comparable angle-accuracy guarantees only away from the boundaries $λ\to0$ or $π/2$ or at discrete depth tradeoffs, our guarantee extends to both boundaries, so the quantum speedup persists there rather than degrading to classical sampling. Numerical experiments confirm the predicted uniform angle accuracy and show low overhead in practice, making them strong candidates for practical amplitude estimation in the early fault-tolerant regime, with applications such as overlap certification, trial-state verification, and Monte Carlo methods.

Comments
20 pages, 2 figures

Related papers

Low-depth amplitude estimation via statistical eigengap estimation

Po-Wei Huang, Bálint Koczor

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.

quant-pharXiv:2603.05475•Mar 6, 2026•0 citations

Low depth algorithms for quantum amplitude estimation

Tudor Giurgică-Tiron, Iordanis Kerenidis, Farrokh Labib +2 more

We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For β∈(0,1] , our algorithms require N=O~(1ϵ1+β) oracle calls and require the oracle to be called sequentially D=O(1ϵ1−β) times to perform amplitude estimation within additive error ϵ . These algorithms interpolate between the classical algorithm (β=1) and the standard quantum algorithm ( β=0 ) and achieve a tradeoff ND=O(1/ϵ2) . These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits.The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for β∈(0,1] and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete β=q/k where k≥2 is the number of distinct coprime moduli used by the algorithm and 1≤q≤k−1 , and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.

arXiv:2012.03348•Quantum•Jun 27, 2022•71 citations

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

Kohei Oshio, Kaito Wada, Naoki Yamamoto

Quantum amplitude estimation is one of the core subroutines in quantum algorithms. This paper gives a parallelized amplitude estimation (PAE) algorithm that simultaneously achieves near-Heisenberg scaling in the total number of queries and sub-linear scaling in the circuit depth, with respect to the estimation precision. The algorithm is composed of a global GHZ state followed by separated low-depth Grover circuits optimized by quantum signal processing techniques; the number of qubits in the GHZ state and the depth of each circuit is tunable as a trade-off way, which particularly enables even near-Heisenberg-limited and logarithmic-depth algorithm for amplitude estimation. We prove that this trade-off scaling is nearly optimal with use of the parallel quantum adversary method, against folklore on the impossibility of efficient parallelization in amplitude estimation. The proposed algorithm has a form of distributed quantum computing, which may be suitable for device implementation.

arXiv:2508.06121•Aug 8, 2025•0 citations

Maximum-Likelihood Amplitude Estimation for Quantum Monte Carlo Integration on Trapped-Ion Hardware: Convergence, Noise-Floor Saturation, Depth-Dependent Bias

Aditi Lal, Alex Khan, Rut Lineswala +1 more

Quantum Amplitude Estimation promises to accelerate Monte Carlo integration by replacing the classical $\varepsilon \propto N^{-1/2}$ sampling law with the Heisenberg-limited $\varepsilon \propto N^{-1}$ scaling, but whether any part of that advantage survives on present-day hardware is an empirical question. We report a systematic experimental benchmark of a Maximum-Likelihood Amplitude Estimation QMC pipeline on IonQ trapped-ion processors, comprising 60 hardware trials on IonQ Forte-1 across five settings(5 & 9 qubits, 100-200 shots per depth, linear & exponential amplification schedules, ~113 device-hours), together with 100 trials on IonQ Aria-1 & Forte-1 noise models at 5, 9 & 19 qubits. The pipeline combines controlled-$R_y$ rotational state preparation, Grover-based amplitude amplification and maximum-likelihood inference and is benchmarked against $b_{\max}^{-1}\!\int_0^{b_{\max}}\!\sin^2\!x\,\mathrm{d}x$ with $b_{\max}=π/5$ ,given results emerge. First, the noiseless limit it attains $\varepsilon \propto N^{-0.88}$, close to the Heisenberg-scaling reference, reducing the error 54-74x over a 133x increase in oracle calls. Second, scaling does not survive on hardware. Every noisy backend saturates at an error floor of (2-5)x 10^{-2}, with fitted exponents of 0.04-0.15 on Forte-1 linear schedules and $α\le\!0$ on the vendor noise models: beyond the optimal shallow depth, however, deeper amplification provides no sustained accuracy gain and instead returns to the noise floor. Forte-1 hardware also outperformed IonQ's own Aria-1 noise model at every depth $m \ge 2$, indicating that vendor noise models are bad predictors of MLAE accuracy. The practical implication for UQ is that on current devices the useful operating point is a shallow, schedule-tuned amplification depth chosen so that the deepest circuit lands near p~1/2 not the deepest schedule the coherence budget allows.

quant-pharXiv:2609.25992•Sep 23, 2026•0 citations

Low-depth Amplitude Estimation without Really Trying

Dinh-Long Vu, Bin Cheng, Patrick Rebentrost

Standard quantum amplitude estimation algorithms provide quadratic speedup to Monte-Carlo simulations but require a circuit depth that scales as inverse of the estimation error. In view of the shallow depth in near-term devices, the precision achieved by these algorithms would be low. In this article, we bypass this limitation by performing the classical Monte-Carlo method on the quantum algorithm itself, achieving a higher than classical precision using low-depth circuits. We require the quantum algorithm to be weakly biased in order to avoid error accumulation during this process. Our method is parallel and can be as weakly biased as the constituent algorithm in some cases.

arXiv:2410.01173•ACM Transactions on Quantum Computing•Jul 26, 2025•0 citations

Quantum Amplitude Estimation in the Presence of Noise

Brown, Eric G., Oktay Göktaş, W. K. Tham

Quantum Amplitude Estimation (QAE) -- a technique by which the amplitude of a given quantum state can be estimated with quadratically fewer queries than by standard sampling -- is a key sub-routine in several important quantum algorithms, including Grover search and Quantum Monte-Carlo methods. An obstacle to implementing QAE in near-term noisy intermediate-scale quantum (NISQ) devices has been the need to perform Quantum Phase Estimation (QPE) -- a costly procedure -- as a sub-routine. This impediment was lifted with various QPE-free methods of QAE, wherein Grover queries of varying depths / powers (often according to a "schedule") are followed immediately by measurements and classical post-processing techniques like maximum likelihood estimation (MLE). Existing analyses as to the optimality of various query schedules in these QPE-free QAE schemes have hitherto assumed noise-free systems. In this work, we analyse QPE-free QAE under common noise models that may afflict NISQ devices and report on the optimality of various query schedules in the noisy regime. We demonstrate that, given an accurate noise characterization of one's system, one must choose a schedule that balances the trade-off between the greater ideal performance achieved by higher-depth circuits, and the correspondingly greater accumulation of noise-induced error.

arXiv:2006.14145•Jun 25, 2020•11 citations
We develop a class of amplitude estimation algorithms with tunable circuit depth MMM and circuit repetitions NNN, requiring neither ancilla qubits nor controlled Grover operations. For additive error εεε in the Grover angle, they attain the nearly optimal query-depth tradeoff M2N∈O~(ε−2)M^2N\in\widetilde{O}(ε^{-2})M2N∈O(ε−2) uniformly over λ∈[0,π/2]λ\in[0,π/2]λ∈[0,π/2], spanning the full range from classical sampling at M=1M=1M=1 to the Heisenberg limit at M=Θ(ε−1)M=Θ(ε^{-1})M=Θ(ε−1). While prior depth-tunable work establishes comparable angle-accuracy guarantees only away from the boundaries λ→0λ\to0λ→0 or π/2π/2π/2 or at discrete depth tradeoffs, our guarantee extends to both boundaries, so the quantum speedup persists there rather than degrading to classical sampling. Numerical experiments confirm the predicted uniform angle accuracy and show low overhead in practice, making them strong candidates for practical amplitude estimation in the early fault-tolerant regime, with applications such as overlap certification, trial-state verification, and Monte Carlo methods.
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.
We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For β∈(0,1] , our algorithms require N=O~(1ϵ1+β) oracle calls and require the oracle to be called sequentially D=O(1ϵ1−β) times to perform amplitude estimation within additive error ϵ . These algorithms interpolate between the classical algorithm (β=1) and the standard quantum algorithm ( β=0 ) and achieve a tradeoff ND=O(1/ϵ2) . These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits.The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for β∈(0,1] and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete β=q/k where k≥2 is the number of distinct coprime moduli used by the algorithm and 1≤q≤k−1 , and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.
Quantum amplitude estimation is one of the core subroutines in quantum algorithms. This paper gives a parallelized amplitude estimation (PAE) algorithm that simultaneously achieves near-Heisenberg scaling in the total number of queries and sub-linear scaling in the circuit depth, with respect to the estimation precision. The algorithm is composed of a global GHZ state followed by separated low-depth Grover circuits optimized by quantum signal processing techniques; the number of qubits in the GHZ state and the depth of each circuit is tunable as a trade-off way, which particularly enables even near-Heisenberg-limited and logarithmic-depth algorithm for amplitude estimation. We prove that this trade-off scaling is nearly optimal with use of the parallel quantum adversary method, against folklore on the impossibility of efficient parallelization in amplitude estimation. The proposed algorithm has a form of distributed quantum computing, which may be suitable for device implementation.
Quantum Amplitude Estimation promises to accelerate Monte Carlo integration by replacing the classical ε∝N−1/2\varepsilon \propto N^{-1/2}ε∝N−1/2 sampling law with the Heisenberg-limited ε∝N−1\varepsilon \propto N^{-1}ε∝N−1 scaling, but whether any part of that advantage survives on present-day hardware is an empirical question. We report a systematic experimental benchmark of a Maximum-Likelihood Amplitude Estimation QMC pipeline on IonQ trapped-ion processors, comprising 60 hardware trials on IonQ Forte-1 across five settings(5 & 9 qubits, 100-200 shots per depth, linear & exponential amplification schedules, ~113 device-hours), together with 100 trials on IonQ Aria-1 & Forte-1 noise models at 5, 9 & 19 qubits. The pipeline combines controlled-RyR_yRy​ rotational state preparation, Grover-based amplitude amplification and maximum-likelihood inference and is benchmarked against bmax⁡−1 ⁣∫0bmax⁡ ⁣sin⁡2 ⁣x dxb_{\max}^{-1}\!\int_0^{b_{\max}}\!\sin^2\!x\,\mathrm{d}xbmax−1​∫0bmax​​sin2xdx with bmax⁡=π/5b_{\max}=π/5bmax​=π/5 ,given results emerge. First, the noiseless limit it attains ε∝N−0.88\varepsilon \propto N^{-0.88}ε∝N−0.88, close to the Heisenberg-scaling reference, reducing the error 54-74x over a 133x increase in oracle calls. Second, scaling does not survive on hardware. Every noisy backend saturates at an error floor of (2-5)x 10^{-2}, with fitted exponents of 0.04-0.15 on Forte-1 linear schedules and α≤ ⁣0α\le\!0α≤0 on the vendor noise models: beyond the optimal shallow depth, however, deeper amplification provides no sustained accuracy gain and instead returns to the noise floor. Forte-1 hardware also outperformed IonQ's own Aria-1 noise model at every depth m≥2m \ge 2m≥2, indicating that vendor noise models are bad predictors of MLAE accuracy. The practical implication for UQ is that on current devices the useful operating point is a shallow, schedule-tuned amplification depth chosen so that the deepest circuit lands near p~1/2 not the deepest schedule the coherence budget allows.
Standard quantum amplitude estimation algorithms provide quadratic speedup to Monte-Carlo simulations but require a circuit depth that scales as inverse of the estimation error. In view of the shallow depth in near-term devices, the precision achieved by these algorithms would be low. In this article, we bypass this limitation by performing the classical Monte-Carlo method on the quantum algorithm itself, achieving a higher than classical precision using low-depth circuits. We require the quantum algorithm to be weakly biased in order to avoid error accumulation during this process. Our method is parallel and can be as weakly biased as the constituent algorithm in some cases.
Quantum Amplitude Estimation (QAE) -- a technique by which the amplitude of a given quantum state can be estimated with quadratically fewer queries than by standard sampling -- is a key sub-routine in several important quantum algorithms, including Grover search and Quantum Monte-Carlo methods. An obstacle to implementing QAE in near-term noisy intermediate-scale quantum (NISQ) devices has been the need to perform Quantum Phase Estimation (QPE) -- a costly procedure -- as a sub-routine. This impediment was lifted with various QPE-free methods of QAE, wherein Grover queries of varying depths / powers (often according to a "schedule") are followed immediately by measurements and classical post-processing techniques like maximum likelihood estimation (MLE). Existing analyses as to the optimality of various query schedules in these QPE-free QAE schemes have hitherto assumed noise-free systems. In this work, we analyse QPE-free QAE under common noise models that may afflict NISQ devices and report on the optimality of various query schedules in the noisy regime. We demonstrate that, given an accurate noise characterization of one's system, one must choose a schedule that balances the trade-off between the greater ideal performance achieved by higher-depth circuits, and the correspondingly greater accumulation of noise-induced error.