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:2412.13345

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

Simina Brânzei, Nicholas Recker

Published Dec 17, 2024• 0 citations
arXivHTMLPDF

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

DOI
10.48550/arxiv.2412.13345

Related papers

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906•Oct 12, 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•0 citations

Quantum Query Lower Bounds for Triangle-Listing and Spanners

Yu Chen, Ananta Mukherjee, Mingyang Yang

This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of $n$-vertex graphs with $Θ(n)$ triangles on which listing any constant fraction of the triangles requires $Ω(n^{3/2-o(1)})$ quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed $k\ge 7$, constructing a multiplicative $k$-spanner requires $Ω(n^{1+\frac{1}{2μ_k}})$ quantum queries, where $μ_k=k/3+O(1)$. For $k\in\{7,8\}$ the bound is $Ω(n^{5/4})$, which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large $k$ the exponent $1+\frac{3}{2k}$ exceeds the $1+\frac{4}{3k}$ implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.

quant-pharXiv:2609.37091•Sep 30, 2026•0 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

quant-pharXiv:2609.40263•Oct 1, 2026•0 citations

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

Tongyang Li, Weiran Ma, Ziyi Yang +1 more

The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $Ω(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$, there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$, and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{Ω(\log k)}$ for exponentially wide grids, where $n=2^{Θ(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.

quant-pharXiv:2610.16209•Oct 13, 2026•0 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

We are presented with a graph, $G$, on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.

arXiv:2402.18714•Feb 28, 2024•0 citations
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph G=(V,E)G = (V,E)G=(V,E) with nnn vertices and black box access to a function f:V→Rf : V \to \mathbb{R}f:V→R, the goal is 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 oracle queries as possible. We show that the quantum query complexity of local search on GGG is Ω(n34g)Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)Ω(g​n43​​), where ggg is the vertex congestion of the graph. For a βββ-expander with maximum degree ΔΔΔ, this implies a lower bound of Ω(β  n14Δ  log⁡n) Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)Ω(Δ​lognβ​n41​​). 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 Ω(n14log⁡n)Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)Ω(logn​n41​​). This improves upon the best prior quantum lower bound of Ω(n18log⁡n)Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) Ω(lognn81​​) 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(n13)O\bigl( n^{\frac{1}{3}} \bigr)O(n31​) for such graphs.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-Graph Collision, the reduction yields a lower bound matching our upper bound above.
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.
This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of nnn-vertex graphs with Θ(n)Θ(n)Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1))Ω(n^{3/2-o(1)})Ω(n3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥7k\ge 7k≥7, constructing a multiplicative kkk-spanner requires Ω(n1+12μk)Ω(n^{1+\frac{1}{2μ_k}})Ω(n1+2μk​1​) quantum queries, where μk=k/3+O(1)μ_k=k/3+O(1)μk​=k/3+O(1). For k∈{7,8}k\in\{7,8\}k∈{7,8} the bound is Ω(n5/4)Ω(n^{5/4})Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large kkk the exponent 1+32k1+\frac{3}{2k}1+2k3​ exceeds the 1+43k1+\frac{4}{3k}1+3k4​ implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
Subgraph detection asks whether an nnn-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph HHH. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of HHH is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed r≥4r\ge 4r≥4, detecting the clique KrK_rKr​ requires nλr−o(1)n^{λ_r-o(1)}nλr​−o(1) queries, where λ4=19/18λ_4=19/18λ4​=19/18, the exponents λrλ_rλr​ increase strictly with rrr, and λr≥2−42/r+O(1/r)λ_r\ge 2-4\sqrt{2/r}+O(1/r)λr​≥2−42/r​+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph HHH with chromatic number c≥4c\ge 4c≥4. These bounds approach quadratic as ccc grows: for sufficiently large ccc, detection requires n2−O(log⁡log⁡c/c)−o(1)n^{2-O(\sqrt{\log\log c/c})-o(1)}n2−O(loglogc/c​)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,rK_{r,r}Kr,r​ requires nβr−o(1)n^{β_r-o(1)}nβr​−o(1) queries, where β10=181/180β_{10}=181/180β10​=181/180 and βr≥2−O(1/r)β_r\ge 2-O(1/\sqrt{r})βr​≥2−O(1/r​). Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.
The Tarski fixed-point problem asks for a fixed point of a monotone map on a kkk-dimensional grid lattice of width nnn and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of Ω(t)Ω(t)Ω(t) when the dimension is multiplied by ttt and the width remains unchanged, and (ii) a factor of Ω(log⁡m)Ω(\log m)Ω(logm) when the width is multiplied by mmm and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an Ω(klog⁡2n)Ω(k\log^2 n)Ω(klog2n) lower bound for k≥4k\geq 4k≥4, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant α>0α>0α>0, there exists a constant δ(α)>0δ(α)>0δ(α)>0 such that Qε(Tarski(n,k))=Ω(knδ(α))Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})Qε​(Tarski(n,k))=Ω(knδ(α)) whenever k>nαk>n^αk>nα, and in particular, an Ω(kn0.0072)Ω(kn^{0.0072})Ω(kn0.0072) lower bound for k>n2/203k>n^{2/203}k>n2/203, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of (k/log⁡k)Ω(log⁡k)(k/\log k)^{Ω(\log k)}(k/logk)Ω(logk) for exponentially wide grids, where n=2Θ(k)n=2^{Θ(k)}n=2Θ(k). The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.
We are presented with a graph, GGG, on nnn vertices with mmm edges whose edge set is unknown. Our goal is to learn the edges of GGG with as few queries to an oracle as possible. When we submit a set SSS of vertices to the oracle, it tells us whether or not SSS induces at least one edge in GGG. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of O(mlog⁡n)O(m \log n)O(mlogn) for a general graph GGG with mmm edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where GGG has maximum degree ddd and is O(1)O(1)O(1)-colorable, Montanaro and Shao presented an algorithm that learns the edges of GGG in at most O~(d2m3/4)\tilde{O}(d^2m^{3/4})O~(d2m3/4) quantum queries. This gives an upper bound of O~(m3/4)\tilde{O}(m^{3/4})O~(m3/4) quantum queries when GGG is a matching or a Hamiltonian cycle, which is far away from the lower bound of Ω(m)Ω(\sqrt{m})Ω(m​) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where GGG has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O~(m)\tilde{O}(\sqrt{m})O~(m​) quantum queries, matching the theoretical lower bound up to logarithmic factors.