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:2012.03348 · Quantum

Low depth algorithms for quantum amplitude estimation

Tudor Giurgică-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, William J. Zeng

Published Jun 27, 2022• 97 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2022-06-27-745

Related papers

Nearly Optimal Amplitude Estimation at any Depth

Jona Erle, Bálint Koczor

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.

quant-pharXiv:2608.24434•Aug 26, 2026•4 citations

Low-depth amplitude estimation on a trapped-ion quantum computer

Tudor Giurgică-Tiron, Sonika Johri, Iordanis Kerenidis +6 more

Amplitude estimation (AE) is a fundamental quantum algorithmic primitive that enables quantum computers to achieve quadratic speedups for a large class of statistical estimation problems, including Monte Carlo methods. Recent works have succeeded in somewhat reducing the necessary resources for AE by trading off some of the speedup for lower depth circuits, but high quality qubits are still needed for demonstrating such algorithms. Here, we report the results of an experimental demonstration of AE on a state-of-the-art trapped ion quantum computer. AE was used to estimate the inner product of randomly chosen four-dimensional unit vectors, and the low-depth AE algorithms were based on the maximum likelihood estimation (MLE) and the Chinese remainder theorem (CRT) techniques. Significant improvements in accuracy were observed for the MLE based approach when deeper quantum circuits were taken into account, including circuits with more than 90 two-qubit gates and depth 60, achieving a mean additive estimation error on the order of ${10}^{\ensuremath{-}2}$. The CRT based approach was found to provided accurate estimates for many of the data points but was less robust against noise on average. Last, we analyze two more AE algorithms that take into account the specifics of the hardware noise to further improve the results.

arXiv:2109.09685•Physical Review Research•Jul 13, 2022•23 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•5 citations

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•6 citations

Benchmarking Amplitude Estimation on a Superconducting Quantum Computer

Salvatore Certo, Anh Dung Pham, Daniel Beaulieu

Amplitude Estimation (AE) is a critical subroutine in many quantum algorithms, allowing for a quadratic speedup in various applications like those involving estimating statistics of various functions as in financial Monte Carlo simulations. Much work has gone into devising methods to efficiently estimate the amplitude of a quantum state without expensive operations like the Quantum Fourier Transform (QFT), which is especially prohibitive given the constraints of current NISQ devices. Newer methods have reduced the number of operations required on a quantum computer and are the most promising near-term implementations of the AE subroutine. While it remains to be seen the exact circuit requirements for a quantum advantage in applications relying on AE, it is necessary to continue to benchmark the algorithm's performance on current quantum computers and the circuit costs associated with such subroutines. Given these considerations, we expand on results from previous experiments in using Maximum Likelihood Estimation (MLE) to approximate the amplitude of a quantum state and provide empirical upper bounds on the current feasible circuit depths for AE on a superconducting quantum computer. Our results show that MLE using optimally-compiled circuits can currently outperform naive sampling for up to 3 Grover Iterations with a circuit depth of 131, which is higher than reported in other experimental results. This functional benchmark is one of many that will be continually monitored against current quantum hardware to measure the necessary progress towards quantum advantage.

arXiv:2201.06987•Jan 18, 2022•7 citations

The maximum-likelihood quantum amplitude estimation algorithm provides the best tradeoff between accuracy and circuit depth among quantum solutions for integral estimation

Marco Maronese, Massimiliano Incudini, Luca Asproni +1 more

The approximation of an integral with numerical integration methods is a relevant problem in many fields, from finance to chemistry. Monte Carlo methods are a family of methods widely used for numerical integration but which are not always applicable to industrial tasks. Instead, there are quantum computing methods such as Quantum Amplitude Estimation able to offer a speed-up compared to the Monte Carlo methods for numerical integration which promise a significant impact, especially in finance. The Quantum Amplitude Estimation algorithm is a fundamental quantum algorithm with the potential to achieve a quadratic speed-up. Unfortunately, being competitive over classical Monte Carlo methods would require hardware performances currently not available. Therefore, alternative methods have been developed in order to exploit fewer resources while maintaining an advantageous theoretical scaling. We present a comparison between the standard QAE algorithm and two NISQ-friendly versions of the QAE on a numerical integration task. The Monte Carlo technique of Metropolis-Hastings instead is used as a classical benchmark. The scaling of the different algorithms are evaluated in terms of estimation error as a function of the number of samples, computational time, and length of the quantum circuits required by the quantum solutions. The conclusion highlights that an alternative approach is preferable with respect to employng the phase estimation routine. Indeed, the maximum likelihood estimation guarantees the best trade-off between the length of the quantum circuits and the precision in the integral estimation.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•3 citations
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.
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 (AE) is a fundamental quantum algorithmic primitive that enables quantum computers to achieve quadratic speedups for a large class of statistical estimation problems, including Monte Carlo methods. Recent works have succeeded in somewhat reducing the necessary resources for AE by trading off some of the speedup for lower depth circuits, but high quality qubits are still needed for demonstrating such algorithms. Here, we report the results of an experimental demonstration of AE on a state-of-the-art trapped ion quantum computer. AE was used to estimate the inner product of randomly chosen four-dimensional unit vectors, and the low-depth AE algorithms were based on the maximum likelihood estimation (MLE) and the Chinese remainder theorem (CRT) techniques. Significant improvements in accuracy were observed for the MLE based approach when deeper quantum circuits were taken into account, including circuits with more than 90 two-qubit gates and depth 60, achieving a mean additive estimation error on the order of ${10}^{\ensuremath{-}2}$. The CRT based approach was found to provided accurate estimates for many of the data points but was less robust against noise on average. Last, we analyze two more AE algorithms that take into account the specifics of the hardware noise to further improve the results.
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.
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.
Amplitude Estimation (AE) is a critical subroutine in many quantum algorithms, allowing for a quadratic speedup in various applications like those involving estimating statistics of various functions as in financial Monte Carlo simulations. Much work has gone into devising methods to efficiently estimate the amplitude of a quantum state without expensive operations like the Quantum Fourier Transform (QFT), which is especially prohibitive given the constraints of current NISQ devices. Newer methods have reduced the number of operations required on a quantum computer and are the most promising near-term implementations of the AE subroutine. While it remains to be seen the exact circuit requirements for a quantum advantage in applications relying on AE, it is necessary to continue to benchmark the algorithm's performance on current quantum computers and the circuit costs associated with such subroutines. Given these considerations, we expand on results from previous experiments in using Maximum Likelihood Estimation (MLE) to approximate the amplitude of a quantum state and provide empirical upper bounds on the current feasible circuit depths for AE on a superconducting quantum computer. Our results show that MLE using optimally-compiled circuits can currently outperform naive sampling for up to 3 Grover Iterations with a circuit depth of 131, which is higher than reported in other experimental results. This functional benchmark is one of many that will be continually monitored against current quantum hardware to measure the necessary progress towards quantum advantage.
The approximation of an integral with numerical integration methods is a relevant problem in many fields, from finance to chemistry. Monte Carlo methods are a family of methods widely used for numerical integration but which are not always applicable to industrial tasks. Instead, there are quantum computing methods such as Quantum Amplitude Estimation able to offer a speed-up compared to the Monte Carlo methods for numerical integration which promise a significant impact, especially in finance. The Quantum Amplitude Estimation algorithm is a fundamental quantum algorithm with the potential to achieve a quadratic speed-up. Unfortunately, being competitive over classical Monte Carlo methods would require hardware performances currently not available. Therefore, alternative methods have been developed in order to exploit fewer resources while maintaining an advantageous theoretical scaling. We present a comparison between the standard QAE algorithm and two NISQ-friendly versions of the QAE on a numerical integration task. The Monte Carlo technique of Metropolis-Hastings instead is used as a classical benchmark. The scaling of the different algorithms are evaluated in terms of estimation error as a function of the number of samples, computational time, and length of the quantum circuits required by the quantum solutions. The conclusion highlights that an alternative approach is preferable with respect to employng the phase estimation routine. Indeed, the maximum likelihood estimation guarantees the best trade-off between the length of the quantum circuits and the precision in the integral estimation.