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.