Sharp Error Bounds On Quantum Boolean Summation In Various Settings

Abstract

We study the quantum summation (QS) algorithm of Brassard, Hoyer, Mosca and Tapp, that approximates the arithmetic mean of a Boolean function defined on N elements. We improve error bounds presented in [1] in the worst-probabilistic setting, and present new error bounds in the average-probabilistic setting. In particular, in the worst-probabilistic setting, we prove that the error of the QS algorithm using $M-1$ queries is $3\pi /(4M)$ with probability $8/{\pi }^2$, which improves the error bound $\pi M^{\{}-1\}+{\pi }^2{M}^{\{}-2\}$ of Brassard et al. We also present bounds with probabilities $p\in (1/2,8/{\pi }^2]$ and show they are sharp for large $M$ and $N{M}^{\{}-1\}$. In the average-probabilistic setting, we prove that the QS algorithm has error of order $$\begin{gathered} \min \\ {M}^{\{}-1\},N^{\{}-1/2\} \end{gathered}$$ if $M$ is divisible by 4. This bound is optimal, as recently shown in [10]. For M not divisible by 4, the QS algorithm is far from being optimal if $M\ll N^{\{}1/2\}$ since its error is pro