{
  "annotation_id": "84fba82c-b699-4452-999f-4134d20532f1",
  "date_created": "2026-03-02T18:02:00.293000Z",
  "date_modified": "2026-03-02T18:02:00.293000Z",
  "file_hash": "40912ac783328e1be292e487ce16bbd14ae4ce4c79b6f3b1d6ed6d541f8c042d",
  "private": false,
  "record": {
    "abstract": "The degree of a polynomial representing (or approximating) a function f is a\nlower bound for the number of quantum queries needed to compute f. This\nobservation has been a source of many lower bounds on quantum algorithms. It\nhas been an open problem whether this lower bound is tight.\n  We exhibit a function with polynomial degree M and quantum query complexity\n\\Omega(M^{1.321...}). This is the first superlinear separation between\npolynomial degree and quantum query complexity. The lower bound is shown by a\nnew, more general version of quantum adversary method.",
    "arxiv_id": "quant-ph/0305028",
    "authors": [
      "Andris Ambainis"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "journal_ref": "Journal of Computer and System Sciences, 72(2): 220-238, 2006",
    "title": "Polynomial degree vs. quantum query complexity",
    "url": "https://arxiv.org/abs/quant-ph/0305028"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "4e716b88-0a0c-4a4c-9375-6d5c52fca1ab",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}