{"id":"arxiv/2609.40263","url":"https://arxiv.org/abs/2609.40263","tags":["quant-ph","cs.DS"],"score":0,"title":"Superlinear Quantum Query Lower Bounds for Subgraph Detection","domain":"quant-ph","source":"arxiv","authors":["Amin Shiraz Gilani","Xingyu Zhou"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}