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:2311.16560 · EPJ Quantum Technology

On the bias in iterative quantum amplitude estimation

Koichi Miyamoto

Published Jun 25, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1140/epjqt/s40507-024-00253-x

Related papers

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

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

Modified Grover operator for quantum amplitude estimation

Shumpei Uno, Yohichi Suzuki, Keigo Hisanaga +4 more

Abstract In this paper, we propose a quantum amplitude estimation method that uses a modified Grover operator and quadratically improves the estimation accuracy in the ideal case, as in the conventional one using the standard Grover operator. Under the depolarizing noise, the proposed method can outperform the conventional one in the sense that it can in principle achieve the ultimate estimation accuracy characterized by the quantum Fisher information in the limit of a large number of qubits, while the conventional one cannot achieve the same value of ultimate accuracy. In general this superiority requires a sophisticated adaptive measurement, but we numerically demonstrate that the proposed method can outperform the conventional one and approach to the ultimate accuracy, even with a simple non-adaptive measurement strategy.

arXiv:2010.11656•New Journal of Physics•Aug 1, 2021•19 citations

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

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

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
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 Gk∣Φ⟩G^{k}|{\Phi}\rangle Gk∣Φ⟩ 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.
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.
Abstract In this paper, we propose a quantum amplitude estimation method that uses a modified Grover operator and quadratically improves the estimation accuracy in the ideal case, as in the conventional one using the standard Grover operator. Under the depolarizing noise, the proposed method can outperform the conventional one in the sense that it can in principle achieve the ultimate estimation accuracy characterized by the quantum Fisher information in the limit of a large number of qubits, while the conventional one cannot achieve the same value of ultimate accuracy. In general this superiority requires a sophisticated adaptive measurement, but we numerically demonstrate that the proposed method can outperform the conventional one and approach to the ultimate accuracy, even with a simple non-adaptive measurement strategy.
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.
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.
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.