A note on quantum lower bounds for local search via congestion and expansion

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\to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v)\le f(u)$ for all $(u,v)\in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $\Omega \left(\frac{n^{\frac{3}{4}}}{\sqrt{g}}\right)$, where $g$ is the vertex congestion of the graph. For a $\beta$-expander with maximum degree $\Delta$, this implies a lower bound of $\Omega \left(\frac{\sqrt{\beta }{n}^{\frac{1}{4}}}{\sqrt{\Delta }\log n}\right)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $\Omega \left(\frac{n^{\frac{1}{4}}}{\sqrt{\log n}}\right)$. This improves upon the best prior quantum lower bound of $\Omega \left(\frac{n^{\frac{1}{8}}}{\log n}\right)$ 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\left(n^{\frac{1}{3}}\right)$ for such graphs.