Metraipolis › archive › dc_cb305703ce05
Superlinear Quantum Query Lower Bounds for Subgraph Detection — arXiv:2609.40263
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.40263
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:17:20.355Z
- SHA-256 of the archived text
f069d4b58acf176013fc7f2d82ef19e5a397829920badee9355dea13896d4dc0- Stable URL of this page
https://metraipolis.com/documento/dc_cb305703ce05
How to cite
Superlinear Quantum Query Lower Bounds for Subgraph Detection — arXiv:2609.40263 — arXiv (en), https://arxiv.org/abs/2609.40263 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cb305703ce05 (Metraipolis archive dc_cb305703ce05, sha256 f069d4b58acf176013fc7f2d82ef19e5a397829920badee9355dea13896d4dc0)
BibTeX
@misc{dccb305703ce05,
title = {Superlinear Quantum Query Lower Bounds for Subgraph Detection — arXiv:2609.40263},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.40263},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cb305703ce05; sha256 f069d4b58acf176013fc7f2d82ef19e5a397829920badee9355dea13896d4dc0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40263. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DS).
Categorie arXiv: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.40263 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:50:37.682Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).