dorsal/arxiv
View SchemaEnhanced algorithms for Local Search
| Authors | Yves F. Verhoeven |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0506019 |
| URL | https://arxiv.org/abs/quant-ph/0506019 |
Abstract
Let G=(V,E) be a finite graph, and f:V->N be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity O(\log n)\cdot d+O(\sqrt{g})\cdot\sqrt{n}, so that we obtain a deterministic query complexity of d+O(\sqrt{g})\cdot\sqrt{n}, where n is the size of G, d is its maximum degree, and $g$ is its genus. We also give a quantum version of our algorithm, whose query complexity is of O(\sqrt{d})+O(\sqrt[4]{g})\cdot\sqrt[4]{n}\log\log n. Our deterministic and quantum algorithms have query complexities respectively smaller than the generic algorithms of Aldous and of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs. Independently from this work, Zhang has recently given a quantum algorithm which finds a local minimum on the planar grid over \{1,...,\sqrt{n}\}^2 using O(\sqrt[4]{n}(\log\log n)^2) queries. Our quantum algorithm can be viewed as a strongly generalized, and slightly enhanced version of this algorithm.
{
"annotation_id": "6f603deb-c8fb-4d49-a2fe-f2fc56fd42d3",
"date_created": "2026-03-02T18:02:16.219000Z",
"date_modified": "2026-03-02T18:02:16.219000Z",
"file_hash": "928c4b1ac3ae55fb6f5c8fa3cd9607fb4334c5265a623ed70a5c9f9725187b44",
"private": false,
"record": {
"abstract": "Let G=(V,E) be a finite graph, and f:V-\u003eN be any function. The Local Search\nproblem consists in finding a local minimum of the function f on G, that is a\nvertex v such that f(v) is not larger than the value of f on the neighbors of v\nin G. In this note, we first prove a separation theorem slightly stronger than\nthe one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This\nresult allows us to enhance a previously known deterministic algorithm for\nLocal Search with query complexity O(\\log n)\\cdot d+O(\\sqrt{g})\\cdot\\sqrt{n},\nso that we obtain a deterministic query complexity of\nd+O(\\sqrt{g})\\cdot\\sqrt{n}, where n is the size of G, d is its maximum degree,\nand $g$ is its genus. We also give a quantum version of our algorithm, whose\nquery complexity is of O(\\sqrt{d})+O(\\sqrt[4]{g})\\cdot\\sqrt[4]{n}\\log\\log n.\nOur deterministic and quantum algorithms have query complexities respectively\nsmaller than the generic algorithms of Aldous and of Aaronson for large classes\nof graphs, including graphs of bounded genus and planar graphs. Independently\nfrom this work, Zhang has recently given a quantum algorithm which finds a\nlocal minimum on the planar grid over \\{1,...,\\sqrt{n}\\}^2 using\nO(\\sqrt[4]{n}(\\log\\log n)^2) queries. Our quantum algorithm can be viewed as a\nstrongly generalized, and slightly enhanced version of this algorithm.",
"arxiv_id": "quant-ph/0506019",
"authors": [
"Yves F. Verhoeven"
],
"categories": [
"quant-ph"
],
"title": "Enhanced algorithms for Local Search",
"url": "https://arxiv.org/abs/quant-ph/0506019"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "da455bfd-4fdf-4063-9cd5-f87d5eb49c56",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}