dorsal/arxiv
View SchemaNew upper and lower bounds for randomized and quantum Local Search
| Authors | Shengyu Zhang |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603034 |
| URL | https://arxiv.org/abs/quant-ph/0603034 |
Abstract
Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0,1}^n and the constant dimensional grids [n]^d, two particular product graphs that recently drew much attention, we get the following tight results: RLS({0,1}^n) = \Theta(2^{n/2}n^{1/2}), QLS({0,1}^n) = \Theta(2^{n/3}n^{1/6}), RLS([n]^d) = \Theta(n^{d/2}) for d \geq 4, QLS([n]^d) = \Theta(n^{d/3}) for d \geq 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [STOC'04], Ambainis (unpublished) and Santha and Szegedy [STOC'04]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]^2, a new quantum algorithm using O(\sqrt{n}(\log\log n)^{1.5}) queries is given. This improves the previous best known upper bound of O(n^{2/3}) (Aaronson, [STOC'04]), and implies that Local Search on grids exhibits different properties in low dimensions.
{
"annotation_id": "87d3c9c8-4f0f-4576-8042-833e3b3b37a4",
"date_created": "2026-03-02T18:02:23.675000Z",
"date_modified": "2026-03-02T18:02:23.675000Z",
"file_hash": "7d51295fda661ef004fa35598519faee367f0f86c6e09f3be5a129864708b279",
"private": false,
"record": {
"abstract": "Local Search problem, which finds a local minimum of a black-box function on\na given graph, is of both practical and theoretical importance to combinatorial\noptimization, complexity theory and many other areas in theoretical computer\nscience. In this paper, we study the problem in the randomized and quantum\nquery models and give new lower and upper bound techniques in both models.\n The lower bound technique works for any graph that contains a product graph\nas a subgraph. Applying it to the Boolean hypercube {0,1}^n and the constant\ndimensional grids [n]^d, two particular product graphs that recently drew much\nattention, we get the following tight results:\n RLS({0,1}^n) = \\Theta(2^{n/2}n^{1/2}), QLS({0,1}^n) = \\Theta(2^{n/3}n^{1/6}),\n RLS([n]^d) = \\Theta(n^{d/2}) for d \\geq 4, QLS([n]^d) = \\Theta(n^{d/3}) for d\n\\geq 6.\n Here RLS(G) and QLS(G) are the randomized and quantum query complexities of\nLocal Search on G, respectively. These improve the previous results by Aaronson\n[STOC\u002704], Ambainis (unpublished) and Santha and Szegedy [STOC\u002704].\n Our new algorithms work well when the underlying graph expands slowly. As an\napplication to [n]^2, a new quantum algorithm using O(\\sqrt{n}(\\log\\log\nn)^{1.5}) queries is given. This improves the previous best known upper bound\nof O(n^{2/3}) (Aaronson, [STOC\u002704]), and implies that Local Search on grids\nexhibits different properties in low dimensions.",
"arxiv_id": "quant-ph/0603034",
"authors": [
"Shengyu Zhang"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "New upper and lower bounds for randomized and quantum Local Search",
"url": "https://arxiv.org/abs/quant-ph/0603034"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0d5653e1-c549-46a4-90dd-56f8c6ae4ca8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}