{
  "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
}