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

arXiv:0806.3437 · Quantum Information and Computation

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

Hang Dinh, Alexander C. Russell

Published Jul 1, 2010• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic10.7-8-5

Related papers

(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Shengyu Zhang

The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $\B^n$, the randomized query complexity of Local Search is $Θ(2^{n/2}n^{1/2})$ and the quantum query complexity is $Θ(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid $[N^{1/d}]^d$, the randomized query complexity is $Θ(N^{1/2})$ for $d \geq 4$ and the quantum query complexity is $Θ(N^{1/3})$ for $d \geq 6$. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04]. Finally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(\log\log N)^{3/2})$ on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.

arXiv:quant-ph/0504085•Electronic colloquium on computational complexity•Apr 12, 2005•2 citations

New upper and lower bounds for randomized and quantum local search

Shengyu Zhang

Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.

arXiv:quant-ph/0603034•ACM Symposium on Theory of Computing (STOC)•May 21, 2006•20 citations

Tight Bounds for Randomized and Quantum Local Search

Shengyu Zhang

The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube $\{0,1\}^n$ and the constant-dimensional grids $[n]^d$, two particular product graphs that recently drew much attention, we get the following tight results: $\text{{\it RLS\/}}(\{0,1\}^n)=\Theta(2^{n/2}n^{1/2})$, $\text{{\it QLS\/}}(\{0,1\}^n)=\Theta(2^{n/3}n^{1/6})$, $\text{{\it RLS\/}}([n]^d)=\Theta(n^{d/2})$ for $d\geq4$, $\text{{\it QLS\/}}([n]^d)=\Theta(n^{d/3})$ for $d\geq6$. Here $\text{{\it RLS\/}}(G)$ and $\text{{\it QLS\/}}(G)$ are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494–501]. Our new algorithms work well when the underlying graph expands slowly. As an application to $[n]^2$, a new quantum algorithm using $O(\sqrt{n}(\log\log n)^{1.5})$ queries is given. This improves the previously best known upper bound of $O(n^{2/3})$ (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474]), and implies that Local Search on grids exhibits different properties in low dimensions.

SIAM Journal on Computing•Jan 1, 2009•10 citations

Lower Bounds for Local Search by Quantum Arguments

Scott Aaronson

The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube $\left\{0,1\right\}^n$, we show a lower bound of $\Omega\left(2^{n/4}/n\right)$ on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of $\Omega\left(2^{n/2}/n^2\right)$ on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension $d\geq3$.

arXiv:quant-ph/0307149•SIAM Journal on Computing•Jun 13, 2004•127 citations

Quantum and classical query complexities of local search are polynomially related

Miklós Sántha, Márió Szegedy

Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E)a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex x ∈ V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form what is the value of f on x? We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous[4] Ald and Aaronson [1] Aar and solves the main open problem in Aar.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•23 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
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.
The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $\B^n$, the randomized query complexity of Local Search is Θ(2n/2n1/2)Θ(2^{n/2}n^{1/2})Θ(2n/2n1/2) and the quantum query complexity is Θ(2n/3n1/6)Θ(2^{n/3}n^{1/6})Θ(2n/3n1/6). We also show that for the constant dimensional grid [N1/d]d[N^{1/d}]^d[N1/d]d, the randomized query complexity is Θ(N1/2)Θ(N^{1/2})Θ(N1/2) for d≥4d \geq 4d≥4 and the quantum query complexity is Θ(N1/3)Θ(N^{1/3})Θ(N1/3) for d≥6d \geq 6d≥6. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04]. Finally we show for [N1/2]2[N^{1/2}]^2[N1/2]2 a new upper bound of O(N1/4(log⁡log⁡N)3/2)O(N^{1/4}(\log\log N)^{3/2})O(N1/4(loglogN)3/2) on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.
Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.
The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0,1}n\{0,1\}^n{0,1}n and the constant-dimensional grids [n]d[n]^d[n]d, two particular product graphs that recently drew much attention, we get the following tight results: $\text{{\it RLS\/}}(\{0,1\}^n)=\Theta(2^{n/2}n^{1/2})$, $\text{{\it QLS\/}}(\{0,1\}^n)=\Theta(2^{n/3}n^{1/6})$, $\text{{\it RLS\/}}([n]^d)=\Theta(n^{d/2})$ for d≥4d\geq4d≥4, $\text{{\it QLS\/}}([n]^d)=\Theta(n^{d/3})$ for d≥6d\geq6d≥6. Here $\text{{\it RLS\/}}(G)$ and $\text{{\it QLS\/}}(G)$ are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494–501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2[n]^2[n]2, a new quantum algorithm using O(n(log⁡log⁡n)1.5)O(\sqrt{n}(\log\log n)^{1.5})O(n​(loglogn)1.5) queries is given. This improves the previously best known upper bound of O(n2/3)O(n^{2/3})O(n2/3) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465–474]), and implies that Local Search on grids exhibits different properties in low dimensions.
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}n\left\{0,1\right\}^n{0,1}n, we show a lower bound of Ω(2n/4/n)\Omega\left(2^{n/4}/n\right)Ω(2n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2n/2/n2)\Omega\left(2^{n/2}/n^2\right)Ω(2n/2/n2) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension d≥3d\geq3d≥3.
Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E)a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex x ∈ V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form what is the value of f on x? We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous[4] Ald and Aaronson [1] Aar and solves the main open problem in Aar.
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.