Sharp Error Bounds on Quantum Boolean Summation in Various Settings

Kwas, Marek; Wozniakowski, Henryk

Sharp Error Bounds on Quantum Boolean Summation in Various Settings

Authors

Description

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π/(4M)$ with probability $8/π^2$, which improves the error bound $πM^{-1} + π^2 M^{-2}$ of Brassard et al. We also present bounds with probabilities $p\in (1/2, 8/π^2]$ and show they are sharp for large $M$ and $NM^{-1}$. In the average-probabilistic setting, we prove that the QS algorithm has error of order $\min\{M^{-1}, N^{-1/2}\}$ 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 proportional to $M^{-1}^$.
32 pages, 2 figures