On a Problem in Quantum Summation

Abstract

We consider the computation of the mean of sequences in the quantum model of computation. We determine the query complexity in the case of sequences which satisfy a $p$-summability condition for $1\le p<2$. This settles a problem left open in Heinrich (2001).

21 pages, paper submitted to the Journal of Complexity

References in corpus (5)

• Quantum Lower Bounds by Polynomials
• Basic concepts in quantum computation
• Introduction to Quantum Algorithms
• Quantum Sub-Gaussian Mean Estimator
• Fast quantum algorithms for numerical integrals and stochastic processes