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 $Ω(2^{n/2 - o(1)})$ 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 $Ω(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 $Ω(N^{1/2}/d\log N)$ and $Ω(N^{1/4}/\sqrt{d\log N})$ , respectively.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 $Ω(2^{n/2 - o(1)})$ 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 $Ω(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 $Ω(N^{1/2}/d\log N)$ and $Ω(N^{1/4}/\sqrt{d\log N})$, respectively.

arXiv:0806.3437Jun 20, 20080 citations

On quantum lower bounds for local search via congestion and expansion

Simina Brânzei, Nicholas Recker

Information Processing LettersOct 1, 20260 citations

Quantum search of matching on signed graphs

Etsuo Segawa, Yusuke Yoshie

arXiv:2007.07223Quantum Information ProcessingMay 1, 20215 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.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.

Quantum Information and ComputationJul 1, 20100 citations

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

Simina Brânzei, Nicholas Recker

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) \leq 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 $Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$ , where $g$ is the vertex congestion of the graph. For a $β$ -expander with maximum degree $Δ$ , this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. 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 $Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$ . This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ 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\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.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) \leq 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 $Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $β$-expander with maximum degree $Δ$, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. 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 $Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ 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\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.

arXiv:2412.13345Dec 17, 20240 citations

Ω(2^{n/2 - o(1)})

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

Ω(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

Ω(N^{1/2}/d\log N)

and

Ω(N^{1/4}/\sqrt{d\log N})

, respectively.

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)

G

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.

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) \leq 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

Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)

, where

g

is the vertex congestion of the graph. For a

β

-expander with maximum degree

Δ

, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. 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

Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)

. This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ 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\bigl( n^{\frac{1}{3}} \bigr)

for such graphs.