Superlinear Quantum Query Lower Bounds for Subgraph Detection
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≥ 4, detecting the clique Kr requires nλr−o(1) queries, where λ4=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 n2−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 Kr,r requires nβr−o(1) queries, where β10=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.
Related
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Improved Quantum Query Bounds for Boolean Matrix Product Verification
- Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
- Tight bounds for hybrid quantum-classical query algorithms
- Quantum Query Lower Bounds for Triangle-Listing and Spanners
BibTeX
@misc{gilani2026superlinear,
title = {{Superlinear Quantum Query Lower Bounds for Subgraph Detection}},
author = {Amin Shiraz Gilani and Xingyu Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40263},
eprint = {2609.40263},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40263},
}
RIS
TY - UNPB
TI - Superlinear Quantum Query Lower Bounds for Subgraph Detection
AU - Amin Shiraz Gilani
AU - Xingyu Zhou
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.40263
UR - https://arxiv.org/abs/2609.40263
AB - 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 λ_4=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 β_10=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.
ER -