arXiv · Sep 30, 2026
Superlinear Quantum Query Lower Bounds for Subgraph Detection
By 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≥ 4, detecting the clique K_r requires n^(λ_r-o(1)) queries, where λ₄=19/18, the exponents λ_r increase strictly with r, and λ_r≥ 2-4√2/r+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph H with chromatic number c≥ 4. These bounds approach quadratic as c grows: for sufficiently large c, detection requires n^2-O(√loglog 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 β₁₀=181/180 and β_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.