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:1912.05559 · npj Quantum Information

Iterative quantum amplitude estimation

Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner

Published Mar 19, 2021• 214 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41534-021-00379-1

Related papers

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 Refinement Quantum Amplitude Estimation

Yoshiyuki Saito, Ningyi Xie, Jungpil Shin +3 more

Quantum Amplitude Estimation (QAE) is an important quantum algorithm that has the potential to quadratically speed up Monte Carlo based calculations.In this paper, we present a variant of the QAE without Phase Estimation Algorithm called Iterative Refinement QAE (IRQAE). IRQAE can refine the current estimation to a more accurate estimation iteratively, hence it can provide an estimation with arbitrary required accuracy ∊. The key idea of IRQAE is to use a rotation gate to create a quantum state for samplings with the current estimation. Using this idea, we show that IRQAE can provide a highly accurate estimation with lower classical computational complexity and with the same quantum computational complexity compared to state-of-the-art QAEs without phase estimation using numerical experiments. We prove that the computational complexity of IRQAE of the quantum part is O(1/∊) and the classical one is O(1/∊). The quantum cost gives a quadratic advantage over that of the classical Monte Carlo simulation.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 18, 2023•1 citation

On the bias in iterative quantum amplitude estimation

Koichi Miyamoto

Abstract Quantum amplitude estimation (QAE) is a pivotal quantum algorithm to estimate the squared amplitude a of the target basis state in a quantum state $|{\Phi}\rangle $ | Φ 〉 . Various improvements on the original quantum phase estimation-based QAE have been proposed for resource reduction. One of such improved versions is iterative quantum amplitude estimation (IQAE), which outputs an estimate â of a through the iterated rounds of the measurements on the quantum states like $G^{k}|{\Phi}\rangle $ G k | Φ 〉 , with the number k of operations of the Grover operator G (the Grover number) and the shot number determined adaptively. This paper investigates the bias in IQAE. Through the numerical experiments to simulate IQAE, we reveal that the estimate by IQAE is biased and the bias is enhanced for some specific values of a. We see that the termination criterion in IQAE that the estimated accuracy of â falls below the threshold is a source of the bias. Besides, we observe that $k_{\mathrm{fin}}$ k fin , the Grover number in the final round, and $f_{\mathrm{fin}}$ f fin , a quantity affecting the probability distribution of measurement outcomes in the final round, are the key factors to determine the bias, and the bias enhancement for specific values of a is due to the skewed distribution of $(k_{\mathrm{fin}},f_{\mathrm{fin}})$ ( k fin , f fin ) . We also present a bias mitigation method: just re-executing the final round with the Grover number and the shot number fixed.

arXiv:2311.16560•EPJ Quantum Technology•Jun 25, 2024•1 citation

Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal

Shion Fukuzawa, Christopher Ho, Sandy Irani +1 more

In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.

arXiv:2208.14612•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•6 citations

Real quantum amplitude estimation

Alberto Manzano, Daniele Musso, Álvaro Leitao

Abstract We introduce the Real Quantum Amplitude Estimation (RQAE) algorithm, an extension of Quantum Amplitude Estimation (QAE) which is sensitive to the sign of the amplitude. RQAE is an iterative algorithm which offers explicit control over the amplification policy through an adjustable parameter. We provide a rigorous analysis of the RQAE performance and prove that it achieves a quadratic speedup, modulo logarithmic corrections, with respect to unamplified sampling. Besides, we corroborate the theoretical analysis with a set of numerical experiments.

arXiv:2204.13641•EPJ Quantum Technology•Feb 3, 2023•16 citations

Quantum Fourier Iterative Amplitude Estimation

Jorge J. Martínez de Lejarza, Michele Grossi, Leandro Cieri +1 more

Monte Carlo integration is a widely used numerical method for approximating integrals, which is often computationally expensive. In recent years, quantum computing has shown promise for speeding up Monte Carlo integration, and several quantum algorithms have been proposed to achieve this goal. In this paper, we present an application of Quantum Machine Learning (QML) and Grover's amplification to build a new quantum algorithm for estimating Monte Carlo integrals. Our method, which we call Quantum Fourier Iterative Amplitude Estimation (QFIAE), decomposes the target function into its Fourier series using a Parametrized Quantum Circuit (PQC), specifically a Quantum Neural Network (QNN), and then inte- grates each trigonometric component using Iterative Quantum Amplitude Estimation (IQAE). This approach builds on Fourier Quantum Monte Carlo Integration (FQMCI) method, which also decomposes the target function into its Fourier series, but QFIAE avoids the need for numerical integration of Fourier coefficients. This approach reduces the computational load while maintaining the quadratic speedup achieved by IQAE. To evaluate the performance of QFIAE, we apply it to a test function corresponding to a particle physics scattering process and compare its accuracy with other quantum integration methods and the analytic result. Our results show that QFIAE achieves comparable accuracy while being suitable for execution on real hardware. We also demonstrate how the accuracy of QFIAE improves by increasing the number of terms in the Fourier series.

arXiv:2305.01686•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations
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.
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.
Quantum Amplitude Estimation (QAE) is an important quantum algorithm that has the potential to quadratically speed up Monte Carlo based calculations.In this paper, we present a variant of the QAE without Phase Estimation Algorithm called Iterative Refinement QAE (IRQAE). IRQAE can refine the current estimation to a more accurate estimation iteratively, hence it can provide an estimation with arbitrary required accuracy ∊. The key idea of IRQAE is to use a rotation gate to create a quantum state for samplings with the current estimation. Using this idea, we show that IRQAE can provide a highly accurate estimation with lower classical computational complexity and with the same quantum computational complexity compared to state-of-the-art QAEs without phase estimation using numerical experiments. We prove that the computational complexity of IRQAE of the quantum part is O(1/∊) and the classical one is O(1/∊). The quantum cost gives a quadratic advantage over that of the classical Monte Carlo simulation.
Abstract Quantum amplitude estimation (QAE) is a pivotal quantum algorithm to estimate the squared amplitude a of the target basis state in a quantum state $|{\Phi}\rangle $ | Φ 〉 . Various improvements on the original quantum phase estimation-based QAE have been proposed for resource reduction. One of such improved versions is iterative quantum amplitude estimation (IQAE), which outputs an estimate â of a through the iterated rounds of the measurements on the quantum states like $G^{k}|{\Phi}\rangle $ G k | Φ 〉 , with the number k of operations of the Grover operator G (the Grover number) and the shot number determined adaptively. This paper investigates the bias in IQAE. Through the numerical experiments to simulate IQAE, we reveal that the estimate by IQAE is biased and the bias is enhanced for some specific values of a. We see that the termination criterion in IQAE that the estimated accuracy of â falls below the threshold is a source of the bias. Besides, we observe that kfink_{\mathrm{fin}}kfin​ k fin , the Grover number in the final round, and ffinf_{\mathrm{fin}}ffin​ f fin , a quantity affecting the probability distribution of measurement outcomes in the final round, are the key factors to determine the bias, and the bias enhancement for specific values of a is due to the skewed distribution of (kfin,ffin)(k_{\mathrm{fin}},f_{\mathrm{fin}})(kfin​,ffin​) ( k fin , f fin ) . We also present a bias mitigation method: just re-executing the final round with the Grover number and the shot number fixed.
In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is log queries, providing a speedup of a factor of 1/ε over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) [1] was introduced with a near-optimal query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that maintains the asymptotically optimal query complexity while retaining small constant factors. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.
Abstract We introduce the Real Quantum Amplitude Estimation (RQAE) algorithm, an extension of Quantum Amplitude Estimation (QAE) which is sensitive to the sign of the amplitude. RQAE is an iterative algorithm which offers explicit control over the amplification policy through an adjustable parameter. We provide a rigorous analysis of the RQAE performance and prove that it achieves a quadratic speedup, modulo logarithmic corrections, with respect to unamplified sampling. Besides, we corroborate the theoretical analysis with a set of numerical experiments.
Monte Carlo integration is a widely used numerical method for approximating integrals, which is often computationally expensive. In recent years, quantum computing has shown promise for speeding up Monte Carlo integration, and several quantum algorithms have been proposed to achieve this goal. In this paper, we present an application of Quantum Machine Learning (QML) and Grover's amplification to build a new quantum algorithm for estimating Monte Carlo integrals. Our method, which we call Quantum Fourier Iterative Amplitude Estimation (QFIAE), decomposes the target function into its Fourier series using a Parametrized Quantum Circuit (PQC), specifically a Quantum Neural Network (QNN), and then inte- grates each trigonometric component using Iterative Quantum Amplitude Estimation (IQAE). This approach builds on Fourier Quantum Monte Carlo Integration (FQMCI) method, which also decomposes the target function into its Fourier series, but QFIAE avoids the need for numerical integration of Fourier coefficients. This approach reduces the computational load while maintaining the quadratic speedup achieved by IQAE. To evaluate the performance of QFIAE, we apply it to a test function corresponding to a particle physics scattering process and compare its accuracy with other quantum integration methods and the analytic result. Our results show that QFIAE achieves comparable accuracy while being suitable for execution on real hardware. We also demonstrate how the accuracy of QFIAE improves by increasing the number of terms in the Fourier series.