Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

Hang Dinh, Alexander C. Russell

Published Aug 27, 2008• 22 citations
Publisher
DOI
10.1007/978-3-540-85363-3_31

Related papers

Search on vertex-transitive graphs by lackadaisical quantum walk

Mason L. Rhodes, Thomas G. Wong

arXiv:2002.11227•Quantum Information Processing•Sep 1, 2020•27 citations

Quantum and randomized lower bounds for local search on vertex-transitive graphs

Hang Dinh, Alexander C. Russell

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 $\Omega(2^{n/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 $\Omega(2^{n/2}/n^2)$ 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 $\Omega\left({\sqrt{N}}/{d\log N}\right)$ and $\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)$, respectively.

arXiv:0806.3437•Quantum Information and Computation•Jul 1, 2010•1 citation

On quantum lower bounds for local search via congestion and expansion

Simina Brânzei, Nicholas Recker

arXiv:2412.13345•Information Processing Letters•Oct 1, 2026•0 citations

Marked vertex search on disordered graphs with Rosenzweig-Porter phases

Sabyasachi Chakraborty, Tilen Cadez, Sonjoy Majumder +1 more

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.

quant-pharXiv:2608.00224•Aug 4, 2026•0 citations

Spectral Lower Bounds for Local Search

Simina Brânzei, Nicholas Recker

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 \to \mathbb{R}$. The local search problem is to find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in 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 $Ω\left( \frac{\sqrt{n}}{t_{mix} \cdot \exp(3σ)}\right)$, where $t_{mix}$ is the mixing time of the chain and $σ= \max_{u,v \in V(G)} \frac{π(v)}{π(u)}.$ 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.

arXiv:2403.06248•Mar 10, 2024•1 citation

Quantum search of matching on signed graphs

Etsuo Segawa, Yusuke Yoshie

arXiv:2007.07223•Quantum Information Processing•May 1, 2021•6 citations
We study the problem of \emph{local search} on a graph. Given a real-valued black-box function fff on the graph's vertices, this is the problem of determining a local minimum of fff---a vertex vvv for which f(v)f(v)f(v) is no more than fff evaluated at any of vvv's neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires Ω(2n/2−o(n))\Omega(2^{n/2 - o(n)} )Ω(2n/2−o(n)) queries to determine a local minima on the nnn-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)\Omega(2^{n/2}/n^2)Ω(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 GGG of NNN vertices and diameter ddd, the randomized and quantum query complexities for local search on GGG are Ω(N/dlog⁡N)\Omega\left({\sqrt{N}}/{d\log N}\right)Ω(N​/dlogN) and Ω(N4/dlog⁡N)\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)Ω(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 ppp, 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)G = (V,E)G=(V,E) and oracle access to a function f:V→Rf : V \to \mathbb{R}f:V→R. The local search problem is to find a vertex vvv that is a local minimum, i.e. with f(v)≤f(u)f(v) \leq f(u)f(v)≤f(u) for all (u,v)∈E(u,v) \in E(u,v)∈E, using as few queries to the oracle as possible. We show that if a graph GGG admits a lazy, irreducible, and reversible Markov chain with stationary distribution πππ, then the randomized query complexity of local search on GGG is Ω(ntmix⋅exp⁡(3σ))Ω\left( \frac{\sqrt{n}}{t_{mix} \cdot \exp(3σ)}\right)Ω(tmix​⋅exp(3σ)n​​), where tmixt_{mix}tmix​ is the mixing time of the chain and σ=max⁡u,v∈V(G)π(v)π(u).σ= \max_{u,v \in V(G)} \frac{π(v)}{π(u)}.σ=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.