  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.

Quantum Physics