Efficient Quantum Algorithm for Weighted Partial Sums and Numerical Integration

Abstract A quantum algorithm is presented 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 , where represents the number of terms in the partial sum. For cases where is a power of two, the unitary construction is straightforward; however, for arbitrary , an efficient quantum algorithm is developed to create the required unitary matrix. Computational examples for evaluation of certain partial sums and numerical integration based on the proposed algorithm are provided. The algorithm is also extended to evaluate partial sums of even or odd components and more complex weighted sums over specified intervals.