Efficient quantum algorithm for weighted partial sums and numerical integration

Abstract

This paper presents a quantum algorithm for efficiently computing partial sums and specific weighted partial sums of quantum state amplitudes. Computation of partial sums has important applications, including numerical integration, cumulative probability distributions, and probabilistic modeling. The proposed quantum algorithm uses a custom unitary construction to achieve the desired partial sums with gate complexity and circuit depth of $O({\log }_{2}M)$, where $M$ represents the number of terms in the partial sum. For cases where $M$ is a power of two, the unitary construction is straightforward; however, for arbitrary $M$, we develop an efficient quantum algorithm to create the required unitary matrix. Computational examples for evaluation certain partial sums and numerical integration based on our proposed algorithm are provided. We also extend the algorithm to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.

arXiv comment14 pages, 3 figures

References in corpus (17)

• Variational Quantum Algorithms
• Quantum Amplitude Amplification and Estimation
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum speedup of Monte Carlo methods
• Amplitude estimation without phase estimation
• Iterative Quantum Amplitude Estimation
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum spectral methods for differential equations
• Low depth algorithms for quantum amplitude estimation
• The Efficient Preparation of Normal Distributions in Quantum Registers
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• Trajectory optimization using quantum computing
• A hybrid classical-quantum algorithm for digital image processing
• Quantum state preparation for multivariate functions
• A quantum approach for digital signal processing
• Hybrid classical-quantum image processing via polar Walsh basis functions
• A quantum approach for optimal control

Cited by in corpus (1)

• A Spectral Quantum Algorithm for Numerical Differentiation and Integration