(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Simple item page
dc.creatorZhang, Shengyu
dc.date2005-04-12
dc.date2005-05-30
dc.date.accessioned2026-07-07T06:12:34Z
dc.date.available2026-07-07T06:12:34Z
dc.descriptionThe 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 many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $\B^n$, the randomized query complexity of Local Search is $Θ(2^{n/2}n^{1/2})$ and the quantum query complexity is $Θ(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid $[N^{1/d}]^d$, the randomized query complexity is $Θ(N^{1/2})$ for $d \geq 4$ and the quantum query complexity is $Θ(N^{1/3})$ for $d \geq 6$. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04]. Finally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(\log\log N)^{3/2})$ on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.
dc.description18 pages, 1 figure. v2: introduction rewritten, references added. v3: a line for grant added. v4: upper bound section rewritten
dc.identifierhttps://arxiv.org/abs/quant-ph/0504085
dc.identifierhttp://arxiv.org/abs/quant-ph/0504085
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/92823
dc.subjectQuantum Physics
dc.title(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids
dc.typetext

Files

Collections

arXiv