A general quantum algorithm for numerical integration

Abstract

Abstract Quantum algorithms have shown their superiority in many application fields. However, a general quantum algorithm for numerical integration, an indispensable tool for processing sophisticated science and engineering issues, is still missing. Here, we first proposed a quantum integration algorithm suitable for any continuous functions that can be approximated by polynomials. More impressively, the algorithm achieves quantum encoding of any integrable functions through polynomial approximation, then constructs a quantum oracle to mark the number of points in the integration area and finally converts the statistical results into the phase angle in the amplitude of the superposition state. The quantum algorithm introduced in this work exhibits quadratic acceleration over the classical integration algorithms by reducing computational complexity from O(N) to O(√N). Our work addresses the crucial impediments for improving the generality of quantum integration algorithm, which provides a meaningful guidance for expanding the superiority of quantum computing.

Keywords

• Quantum algorithm
• Numerical integration
• Phase estimation
• Quadratic acceleration