Sharp Error Bounds on Quantum Boolean Summation in Various Settings
| dc.creator | Kwas, Marek | |
| dc.creator | Wozniakowski, Henryk | |
| dc.date | 2003-03-10 | |
| dc.date.accessioned | 2026-07-07T06:06:17Z | |
| dc.date.available | 2026-07-07T06:06:17Z | |
| dc.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}^$. | |
| dc.description | 32 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0303049 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0303049 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90923 | |
| dc.subject | Quantum Physics | |
| dc.title | Sharp Error Bounds on Quantum Boolean Summation in Various Settings | |
| dc.type | text |