We study the problem of \emph{local search} on a graph. Given a real-valued black-box function f on the graph's vertices, this is the problem of determining a local minimum of f---a vertex v for which f(v) is no more than f evaluated at any of v's neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires Ω(2n/2−o(n)) queries to determine a local minima on the n-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to Ω(2n/2/n2) and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph G of N vertices and diameter d, the randomized and quantum query complexities for local search on G are Ω(N/dlogN) and Ω(4N/dlogN), respectively.
Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erdős-Rényi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site' potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability p, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.
Local search is a powerful heuristic in optimization and computer science, the complexity of which has been studied in the white box and black box models. In the black box model, we are given a graph G=(V,E) and oracle access to a function f:V→R. The local search problem is to find a vertex v that is a local minimum, i.e. with f(v)≤f(u) for all (u,v)∈E, using as few queries to the oracle as possible. We show that if a graph G admits a lazy, irreducible, and reversible Markov chain with stationary distribution π, then the randomized query complexity of local search on G is Ω(tmix⋅exp(3σ)n), where tmix is the mixing time of the chain and σ=maxu,v∈V(G)π(u)π(v). This theorem formally establishes a connection between the query complexity of local search and the mixing time of the fastest mixing Markov chain for the given graph. We also get several corollaries that lower bound the complexity as a function of the spectral gap, one of which slightly improves a lower bound based on spectral gaps from prior work.