Skip to content
Preprint

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Sep 2026 · 2 citations · 30 references
Physics Computer Science

TL;DR

This work proves the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of subgraph detection, and proves an all-ones certificate from a known family when the input bits are sampled independently.

Abstract

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^{\lambda_r-o(1)}$ queries, where $\lambda_4=19/18$, the exponents $\lambda_r$ increase strictly with $r$, and $\lambda_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^{\beta_r-o(1)}$ queries, where $\beta_{10}=181/180$ and $\beta_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.

View source

Similar papers

Preprint Sep 2026

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial...

Pan Peng, Ke-Fan Yu · 0 citations
Preprint Oct 2026

Quantum Query Complexity of Maximum Degree and its Generalizations

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(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...

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro et al. · 2 citations · ⚡1
Preprint Oct 2026

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

The Variational Iterative Rotation Algorithm (VIRAL), a classical local algorithm, is evaluated and the resulting bounds exceed those recently obtained from the Quantum Approximate Optimization Algorithm (QAOA), and the range of girths covered from g=36 to g=66 is extended.

F. Morone, Shivang Rawat, Dries Sels · 1 citation
Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...

Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou · 0 citations
Preprint Sep 2026

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds for large families of sparse graphs with expansion properties and extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

Jacob Imola, Rasmus Pagh, Lukas Retschmeier · 1 citation
Preprint Oct 2026

Optimal Bounds on Spanning Tree Embeddings

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....

Csongor Beke, V. Boskovic, Nina Kamčev et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.