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:2005.05300

Comparison of Amplitude Estimation Algorithms by Implementation

Kwangmin Yu, Hyunkyung Lim, Pooja Rao, Dasol Jin

Published May 8, 2020• 5 citations
arXivHTMLPDF

Abstract

Since the quantum amplitude estimation (QAE) was invented by Brassard et al., 2002, several advanced algorithms have recently been published (Grinko et al., 2019, Aaronson et al, and Suzuki et al., 2020). The main difference between the variants and the original algorithm is that the variants do not need quantum phase estimation (QPE), a key component of the canonical QAE (Brassard et al., 2002), that is composed of many expensive operations on NISQ devices. In this paper, we compare and analyze two of these new QAE approaches (Grinko et al., 2019, and Suzuki et al., 2020) by implementation using the Qiskit package. The comparisons are drawn based on number of oracle queries, quantum circuit depth, and other complexities of implementation for a fixed accuracy. We discuss the strengths and limitations of each algorithm from a computational perspective.

DOI
10.48550/arxiv.2005.05300

Related papers

Quantum amplitude estimation algorithms on IBM quantum devices

Pooja Rao, Kwangmin Yu, Hyunkyung Lim +2 more

Since the publication of the Quantum Amplitude Estimation (QAE) algorithm by Brassard et al., 2002, several variations have been proposed, such as Aaronson et al., 2019, Grinko et al., 2019, and Suzuki et al., 2020. The main difference between the original and the variants is the exclusion of Quantum Phase Estimation (QPE) by the latter. This difference is notable given that QPE is the key component of original QAE, but is composed of many operations considered expensive for the current NISQ era devices. We compare two recently proposed variants (Grinko et al., 2019 and Suzuki et al., 2020) by implementing them on the IBM Quantum device using Qiskit, an open source framework for quantum computing. We analyze and discuss advantages of each algorithm from the point of view of their implementation and performance on a quantum computer.

arXiv:2008.02102•Aug 22, 2020•26 citations

Practical numerical integration on NISQ devices

Kwangmin Yu, Hyunkyung Lim, Pooja Rao

This paper addresses the practical aspects of quantum algorithms used in numerical integration, specifically their implementation on Noisy Intermediate-Scale Quantum (NISQ) devices. Quantum algorithms for numerical integration utilize Quantum Amplitude Estimation (QAE) (Brassard et al., 2002) in conjunction with Grover’s algorithm. However, QAE is daunting to implement on NISQ devices since it typically relies on Quantum Phase Estimation (QPE), which requires many ancilla qubits and controlled operations. To mitigate these challenges, a recently published QAE algorithm (Suzuki et al., 2020), which does not rely on QPE, requires a much smaller number of controlled operations and does not require ancilla qubits. We implement this new algorithm for numerical integration on IBM quantum devices using Qiskit and optimize the circuit on each target device. We discuss the application of this algorithm on two qubits and its scalability to more than two qubits on NISQ devices.

arXiv:2004.05739•Apr 24, 2020•9 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

Iterative quantum amplitude estimation

Dmitry Grinko, Julien Gacon, Christa Zoufal +1 more

We introduce a variant of Quantum Amplitude Estimation (QAE), called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover’s Algorithm, which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation with provably small constant overhead. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.

•Jan 1, 2021•150 citations

Iterative quantum amplitude estimation

Dmitry Grinko, Julien Gacon, Christa Zoufal +1 more

Abstract We introduce a variant of Quantum Amplitude Estimation (QAE) , called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover’s Algorithm , which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation with provably small constant overhead. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.

arXiv:1912.05559•npj Quantum Information•Mar 19, 2021•214 citations

Amplitude Estimation Algorithms and Implementations on Noisy Intermediate-Scale Quantum Devices

Pooja Rao, Kwangmin Yu, Hyunkyung Lim +2 more

We implement two recently published quantum amplitude estimation algorithms on the IBM quantum device to analyze and discuss advantages of each of these algorithms from the perspective of its performance on a quantum device.

OSA Quantum 2.0 Conference•Jan 1, 2020•6 citations
Since the quantum amplitude estimation (QAE) was invented by Brassard et al., 2002, several advanced algorithms have recently been published (Grinko et al., 2019, Aaronson et al, and Suzuki et al., 2020). The main difference between the variants and the original algorithm is that the variants do not need quantum phase estimation (QPE), a key component of the canonical QAE (Brassard et al., 2002), that is composed of many expensive operations on NISQ devices. In this paper, we compare and analyze two of these new QAE approaches (Grinko et al., 2019, and Suzuki et al., 2020) by implementation using the Qiskit package. The comparisons are drawn based on number of oracle queries, quantum circuit depth, and other complexities of implementation for a fixed accuracy. We discuss the strengths and limitations of each algorithm from a computational perspective.
Since the publication of the Quantum Amplitude Estimation (QAE) algorithm by Brassard et al., 2002, several variations have been proposed, such as Aaronson et al., 2019, Grinko et al., 2019, and Suzuki et al., 2020. The main difference between the original and the variants is the exclusion of Quantum Phase Estimation (QPE) by the latter. This difference is notable given that QPE is the key component of original QAE, but is composed of many operations considered expensive for the current NISQ era devices. We compare two recently proposed variants (Grinko et al., 2019 and Suzuki et al., 2020) by implementing them on the IBM Quantum device using Qiskit, an open source framework for quantum computing. We analyze and discuss advantages of each algorithm from the point of view of their implementation and performance on a quantum computer.
This paper addresses the practical aspects of quantum algorithms used in numerical integration, specifically their implementation on Noisy Intermediate-Scale Quantum (NISQ) devices. Quantum algorithms for numerical integration utilize Quantum Amplitude Estimation (QAE) (Brassard et al., 2002) in conjunction with Grover’s algorithm. However, QAE is daunting to implement on NISQ devices since it typically relies on Quantum Phase Estimation (QPE), which requires many ancilla qubits and controlled operations. To mitigate these challenges, a recently published QAE algorithm (Suzuki et al., 2020), which does not rely on QPE, requires a much smaller number of controlled operations and does not require ancilla qubits. We implement this new algorithm for numerical integration on IBM quantum devices using Qiskit and optimize the circuit on each target device. We discuss the application of this algorithm on two qubits and its scalability to more than two qubits on NISQ devices.
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.
We introduce a variant of Quantum Amplitude Estimation (QAE), called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover’s Algorithm, which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation with provably small constant overhead. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.
Abstract We introduce a variant of Quantum Amplitude Estimation (QAE) , called Iterative QAE (IQAE), which does not rely on Quantum Phase Estimation (QPE) but is only based on Grover’s Algorithm , which reduces the required number of qubits and gates. We provide a rigorous analysis of IQAE and prove that it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation with provably small constant overhead. Furthermore, we show with an empirical study that our algorithm outperforms other known QAE variants without QPE, some even by orders of magnitude, i.e., our algorithm requires significantly fewer samples to achieve the same estimation accuracy and confidence level.