The problem of finding a local minimum of a black-box function is central
for understanding local search as well as quantum adiabatic algorithms.
For functions on the Boolean hypercube {0,1}^n, we show a lower bound of
Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to
solve this problem. More surprisingly, our approach, based on Ambainis'
quantum adversary method, also yields a lower bound of Omega(2^{n/2}/n^2)
on the problem's classical randomized query complexity. This improves and
simplifies a 1983 result of Aldous. Finally, in both the randomized and
quantum cases, we give the first nontrivial lower bounds for finding local
minima on grids of constant dimension greater than 2.