Quantum limits on detecting complex patterns in large networks
Superlinear Quantum Query Lower Bounds for Subgraph Detection
Data Structures and Algorithms
Summary
Detecting small patterns within big networks—like finding a specific shape inside a giant web—is an important problem in computing. The authors showed that even the best quantum computers need more than a simple, proportional amount of effort to find these patterns when the pattern is sufficiently complex. They proved this for certain shapes, including large cliques and complex colorings, improving our understanding of quantum algorithms' limits. Their work uses advanced mathematical tools to show that certain network searches require more than linear queries, approaching a quadratic number in some cases.
What this means in practice
- •For quantum algorithm designers: Focus efforts on problems where quantum search speedups surpass proven lower bounds for complex pattern detection, avoiding dead ends on superlinear query tasks.
- •For graph algorithm engineers: Recognize limitations of quantum queries for detecting certain subgraphs when designing efficient network analysis tools using quantum methods.
A theory result. No direct application yet.
Authors
Amin Shiraz Gilani, Xingyu Zhou
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^{λ_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.