{
  "annotation_id": "0b23cef3-8dcd-489d-bc27-7db3c703da68",
  "date_created": "2026-03-02T18:02:15.967000Z",
  "date_modified": "2026-03-02T18:02:15.967000Z",
  "file_hash": "6d99cf79e9794a9eb5b6d5ed167173a146aeafa3dfcc47781f108f3738ecb479",
  "private": false,
  "record": {
    "abstract": "The Local Search problem, which finds a local minimum of a black-box function\non a given graph, is of both practical and theoretical importance to many areas\nin computer science and natural sciences. In this paper, we show that for the\nBoolean hypercube $\\B^n$, the randomized query complexity of Local Search is\n$\\Theta(2^{n/2}n^{1/2})$ and the quantum query complexity is\n$\\Theta(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid\n$[N^{1/d}]^d$, the randomized query complexity is $\\Theta(N^{1/2})$ for $d \\geq\n4$ and the quantum query complexity is $\\Theta(N^{1/3})$ for $d \\geq 6$. New\nlower bounds for lower dimensional grids are also given. These improve the\nprevious results by Aaronson [STOC\u002704], and Santha and Szegedy [STOC\u002704].\nFinally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(\\log\\log\nN)^{3/2})$ on the quantum query complexity, which implies that Local Search on\ngrids exhibits different properties at low dimensions.",
    "arxiv_id": "quant-ph/0504085",
    "authors": [
      "Shengyu Zhang"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "(Almost) tight bounds for randomized and quantum Local Search on   hypercubes and grids",
    "url": "https://arxiv.org/abs/quant-ph/0504085"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "bc62b7bb-8d67-4901-ac5b-aa97bf936bf2",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}