{
  "annotation_id": "935a1b55-f452-4ba8-8846-fc9f4c07e4f9",
  "date_created": "2026-03-02T18:01:59.753000Z",
  "date_modified": "2026-03-02T18:01:59.753000Z",
  "file_hash": "c7cefbe29940b9adac7f55b933a48b742443943fa9c3f81a40bcb78013d0e237",
  "private": false,
  "record": {
    "abstract": "The problem of finding a local minimum of a black-box function is central for\nunderstanding local search as well as quantum adiabatic algorithms. For\nfunctions on the Boolean hypercube {0,1}^n, we show a lower bound of\nOmega(2^{n/4}/n) on the number of queries needed by a quantum computer to solve\nthis problem. More surprisingly, our approach, based on Ambainis\u0027 quantum\nadversary method, also yields a lower bound of Omega(2^{n/2}/n^2) on the\nproblem\u0027s classical randomized query complexity. This improves and simplifies a\n1983 result of Aldous. Finally, in both the randomized and quantum cases, we\ngive the first nontrivial lower bounds for finding local minima on grids of\nconstant dimension greater than 2.",
    "arxiv_id": "quant-ph/0307149",
    "authors": [
      "Scott Aaronson"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Lower Bounds for Local Search by Quantum Arguments",
    "url": "https://arxiv.org/abs/quant-ph/0307149"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "a561f95d-4402-4044-9904-96f81d724b23",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}