{
  "annotation_id": "c6535f76-f8c4-4abf-9de6-45f00aa30207",
  "date_created": "2026-03-02T18:02:41.712000Z",
  "date_modified": "2026-03-02T18:02:41.712000Z",
  "file_hash": "72cfa460b6db714537c1866d5f6882a4994972635e3caf7ebf520ca0f934bc0c",
  "private": false,
  "record": {
    "abstract": "Let X = (x_0,...,x_{n-1})$ be a sequence of n numbers. For \\epsilon \u003e 0, we\nsay that x_i is an \\epsilon-approximate median if the number of elements\nstrictly less than x_i, and the number of elements strictly greater than x_i\nare each less than (1+\\epsilon)n/2. We consider the quantum query complexity of\ncomputing an \\epsilon-approximate median, given the sequence X as an oracle. We\nprove a lower bound of \\Omega(\\min{{1/\\epsilon},n}) queries for any quantum\nalgorithm that computes an \\epsilon-approximate median with any constant\nprobability greater than 1/2. We also show how an \\epsilon-approximate median\nmay be computed with O({1/\\epsilon}\\log({1\\/\\epsilon}) \\log\\log({1/\\epsilon}))\noracle queries, which represents an improvement over an earlier algorithm due\nto Grover. Thus, the lower bound we obtain is essentially optimal. The upper\nand the lower bound both hold in the comparison tree model as well.\n  Our lower bound result is an application of the polynomial paradigm recently\nintroduced to quantum complexity theory by Beals et al. The main ingredient in\nthe proof is a polynomial degree lower bound for real multilinear polynomials\nthat ``approximate\u0027\u0027 symmetric partial boolean functions. The degree bound\nextends a result of Paturi and also immediately yields lower bounds for the\nproblems of approximating the kth-smallest element, approximating the mean of a\nsequence of numbers, and that of approximately counting the number of ones of a\nboolean function. All bounds obtained come within polylogarithmic factors of\nthe optimal (as we show by presenting algorithms where no such optimal or near\noptimal algorithms were known), thus demonstrating the power of the polynomial\nmethod.",
    "arxiv_id": "quant-ph/9804066",
    "authors": [
      "Ashwin Nayak",
      "Felix Wu"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "The quantum query complexity of approximating the median and related   statistics",
    "url": "https://arxiv.org/abs/quant-ph/9804066"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "269526b2-eb0d-4e6b-b6c4-21ea1e68a2af",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}