The 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 combinatorial optimization, complexity theory and quantum computing. In this paper, we give both new lower and upper bound techniques for randomized and quantum query complexities of Local Search. The lower bound technique works for product graphs. Applying the technique to the Boolean hypercube $\B^n$ and the constant dimensional grids $[n]^d$, two particular types of product graphs that recently draw much attention, we get the following tight results.

\[

RLS(\B^n) = \Theta(2^{n/2}n^{1/2}), QLS(\B^n) = \Theta(2^{n/3}n^{1/6}) \]

\[RLS([n]^d) = \Theta(n^{d/2}) \text{ for } d\geq 4, QLS([n]^d) = \Theta(n^{d/3}) \text{

for } d\geq 6.

\]

where $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], and Santha and Szegedy [STOC'04].

Our new Local Search algorithms work well when the underlining graph expands slowly. As an application to the 2-dimensional grid $[n]^2$, a new quantum algorithm using $O(\sqrt{n}(\log\log n)^{1.5})$ time and 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 at low dimensions.

The 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 $\Theta(2^{n/2}n^{1/2})$ and the quantum query complexity is $\Theta(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid $[N^{1/d}]^d$, the randomized query complexity is $\Theta(N^{1/2})$ for $d \geq 4$ and the quantum query complexity is $\Theta(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.

The 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 $\Theta(2^{n/2}n^{1/2})$ and the quantum query

complexity is $\Theta(2^{n/3}n^{1/6})$. We also show that for the

constant dimensional grid $[N^{1/d}]^d$, the randomized query

complexity is $\Theta(N^{1/2})$ for $d \geq 4$ and the quantum

query complexity is $\Theta(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.