Abstract This chapter introduces and analyses two of the most important quantum algorithmic primitives that are used in myriad applications, namely quantum phase estimation and quantum amplitude estimation (QAE). Quantum phase estimation (in the presentation covered in this chapter) uses the quantum Fourier transform, itself an extremely important quantum subroutine. In its original presentation, QAE combines quantum amplitude amplification (a generalisation of the circuit used in Grover’s algorithm) and quantum phase estimation to estimate the amplitude of a quantum state. However, more recent approaches achieve amplitude estimation without phase estimation, which is potentially practically advantageous. This chapter covers both, as well as some important applications of QAE such as quantum Monte Carlo integration and quantum counting.
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.