Quantum amplitude estimation is a numerical integration technique and a candidate for the first operationally used quantum algorithm providing a quantum advantage in the NISQ era. Its main metric is the generated Fisher information per second, as it describes the accuracy of the numerical integration. The development of this metric can be coupled to the quantum volume of the used quantum processor with a phenomenological noise model. Since the increase of the quantum volume seems to follow an exponential pattern, insight in the integration power of quantum amplitude estimation for the upcoming years can be obtained. This shows that quantum amplitude estimation as a numerical integration technique will not provide an advantage for functions without significant improvements to the connectivity, reliability and speed of quantum processors. Beyond that, this method may be used the estimate the development of many more NISQ era algorithms.
A variant of QAE algorithm by Suzuki et al. called maximum likelihood amplitude estimation (MLAE) achieves the amplitude estimation by varying depths of Grover operators and post-processing for maximum likelihood estimation without the additional controlled operations and QFT. However, MLAE requires running multiple circuits of different depths of Grover operators. On the other hand, quantum multi-programming (QMP) is a computing method that executes multiple quantum circuits concurrently on a quantum computer. The quantum circuits executed concurrently can be different and even have different circuit depths. The main motivation of the QMP is that the number of qubits of NISQ computers is much greater than their quantum volume. In this work, using QMP in conjunction with MLAE makes it possible to run MLAE using a single circuit, thus requiring sampling much fewer times. We validate this algorithm for a numerical integration problem using NVIDIA’s open-source platform CUDA Quantum (simulator), Qiskit (simulator) and Quantinuum H2 device.
We demonstrate that the problem of amplitude estimation, a core subroutine used in many quantum algorithms, can be mapped directly to a problem in signal processing called direction of arrival (DOA) estimation. The DOA task is to determine the direction of arrival of an incoming wave with the fewest possible measurements. The connection between amplitude estimation and DOA allows us to make use of the vast amount of signal processing algorithms to post-process the measurements of the Grover iterator at predefined depths. Using an off-the-shelf DOA algorithm called ESPRIT together with a compressed-sensing based sampling approach, we create a phase-estimation free, parallel quantum amplitude estimation (QAE) algorithm with a worst-case sequential query complexity of
∼4.3/ε and a parallel query complexity of
∼0.26/ε at 95% confidence. This performance is statistically equivalent and a
16× improvement over Rall and Fuller [Quantum 7, 937 (2023)], for sequential and parallel query complexity respectively, which to our knowledge is the best published result for amplitude estimation. The approach presented here provides a simple, robust, parallel method to performing QAE, with many possible avenues for improvement borrowing ideas from the wealth of literature in classical signal processing.