dorsal/arxiv
View SchemaSharp Error Bounds on Quantum Boolean Summation in Various Settings
| Authors | Marek Kwas, Henryk Wozniakowski |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0303049 |
| URL | https://arxiv.org/abs/quant-ph/0303049 |
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 $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}^$.
{
"annotation_id": "8cbc9149-a260-4e2a-b37c-f25899c447ba",
"date_created": "2026-03-02T18:01:56.268000Z",
"date_modified": "2026-03-02T18:01:56.268000Z",
"file_hash": "24dcebe8aee5963e9e95b9a132c8f6841c963ec653f4facf48666aacaa6df705",
"private": false,
"record": {
"abstract": "We study the quantum summation (QS) algorithm of Brassard, Hoyer, Mosca and\nTapp, that approximates the arithmetic mean of a Boolean function defined on N\nelements. We improve error bounds presented in [1] in the worst-probabilistic\nsetting, and present new error bounds in the average-probabilistic setting. In\nparticular, in the worst-probabilistic setting, we prove that the error of the\nQS algorithm using $M - 1$ queries is $3\\pi /(4M)$ with probability $8/\\pi^2$,\nwhich improves the error bound $\\pi M^{-1} + \\pi^2 M^{-2}$ of Brassard et al.\nWe also present bounds with probabilities $p\\in (1/2, 8/\\pi^2]$ and show they\nare sharp for large $M$ and $NM^{-1}$. In the average-probabilistic setting, we\nprove that the QS algorithm has error of order $\\min\\{M^{-1}, N^{-1/2}\\}$ if\n$M$ is divisible by 4. This bound is optimal, as recently shown in [10]. For M\nnot divisible by 4, the QS algorithm is far from being optimal if $M \\ll\nN^{1/2}$ since its error is proportional to $M^{-1}^$.",
"arxiv_id": "quant-ph/0303049",
"authors": [
"Marek Kwas",
"Henryk Wozniakowski"
],
"categories": [
"quant-ph"
],
"title": "Sharp Error Bounds on Quantum Boolean Summation in Various Settings",
"url": "https://arxiv.org/abs/quant-ph/0303049"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "35c7ed50-5b95-482c-b2af-d3f161c28bd5",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}