Lower Bounds for Local Search by Quantum Arguments

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}/poly(n)) on the quantum query complexity of this problem,
implying an oracle separation between the complexity classes PLS and
FBQP. More surprisingly, our technique, based on Ambainis' quantum
adversary method, also yields an Omega(2^{n/2}/poly(n)) lower bound on
the problem's classical randomized query complexity. It also yields
lower bounds for hypercubes of constant dimension, for which no lower
bound (classical or quantum) was previously known.