{
  "annotation_id": "f9ca13cd-09d7-43bb-b2c5-c812a0c99b85",
  "date_created": "2026-03-02T18:02:48.537000Z",
  "date_modified": "2026-03-02T18:02:48.537000Z",
  "file_hash": "3feaba8c4e1c53975fd8f14aca267f46231e8faf0b1af9d3c4301c326ad6fafb",
  "private": false,
  "record": {
    "abstract": "We consider the problem where P is an unknown permutation on {0,1,...,2^n -\n1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the\nminimum r \u003e 0 such that P^r(y) = y (where P^r is P composed with itself r\ntimes). Information about P is available only via queries that yield P^x(y)\nfrom any x in {0,1,...,2^m - 1} and y in {0,1,...,2^n - 1} (where m is\npolynomial in n). The main resource under consideration is the number of these\nqueries. We show that the number of queries necessary to solve the problem in\nthe classical probabilistic bounded-error model is exponential in n. This\ncontrasts sharply with the quantum bounded-error model, where a constant number\nof queries suffices.",
    "arxiv_id": "quant-ph/9911124",
    "authors": [
      "Richard Cleve"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "The query complexity of order-finding",
    "url": "https://arxiv.org/abs/quant-ph/9911124"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "bd1c71b7-16ab-46f0-b12e-2d9683b2b0c2",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}