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 $\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

Cited by in corpus (2)

• Complexity of multivariate Feynman-Kac path integration in randomized and quantum settings
• Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces