Abstract
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph G = (V,E) with n vertices and black box access to a function f : V → R, the goal is find a vertex v that is a local minimum, i.e. with f(v) ≤ f(u) for all (u,v) ∈ E, using as few oracle queries as possible. We show that the quantum query complexity of local search on G is Ω( n^3/4/√g ), where g is the vertex congestion of the graph. For a β-expander with maximum degree Δ, this implies a lower bound of Ω(√β n^1/4/√Δ logn ). We obtain these bounds by applying the strong weighted adversary method to a construction by Br\^anzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of Ω(n^1/4/ √logn ). This improves upon the best prior quantum lower bound of Ω( n^1/8/logn) by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of O( n^1/3 ) for such graphs.