{
  "annotation_id": "89e2de9d-40e5-468b-bffc-25a41680e5aa",
  "date_created": "2026-03-02T18:02:03.598000Z",
  "date_modified": "2026-03-02T18:02:03.598000Z",
  "file_hash": "a71013f7cd13c8d79307d3b253ac5c5364b77ac6e225ae18ba1afcd2673a2225",
  "private": false,
  "record": {
    "abstract": "We study the quantum summation QS algorithm of Brassard,\n  Hoyer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean\nfunction defined on $N$ elements. We present sharp error bounds of the QS\nalgorithm in the worst-average setting with the average performance measured in\nthe $L_q$ norm, $q \\in [1,\\infty]$. We prove that the QS algorithm with $M$\nquantum queries, $M\u003cN$, has the worst-average error bounds of the form\n$\\Theta(\\ln M/M)$ for $q=1$, $\\Theta(M^{-1/q})$ for $q\\in (1,\\infty)$, and is\nequal to 1 for $q=\\infty$. We also discuss the asymptotic constants of these\nestimates. We improve the error bounds by using the QS algorithm with\nrepetitions. Using the number of repetitions which is independent of $M$ and\nlinearly dependent on $q$, we get the error bound of order $M^{-1}$ for any $q\n\\in [1,\\infty)$. Since $\\Omega(M^{-1})$ is a lower bound on the worst-average\nerror of any quantum algorithm with $M$ queries, the QS algorithm with\nrepetitions is optimal in the worst-average setting.",
    "arxiv_id": "quant-ph/0311036",
    "authors": [
      "Stefan Heinrich",
      "Marek Kwas",
      "Henryk Wozniakowski"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Boolean Summation with Repetitions in the Worst-Average Setting",
    "url": "https://arxiv.org/abs/quant-ph/0311036"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c3b0006e-bac8-489b-819f-167aebe3b610",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}