Quantum Query Lower Bounds for Triangle-Listing and Spanners
Abstract
This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of n-vertex graphs with Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥ 7, constructing a multiplicative k-spanner requires Ω(n1+1/2μk) quantum queries, where μk=k/3+O(1). For k∈{7,8} the bound is Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large k the exponent 1+3/2k exceeds the 1+4/3k implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
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 Algorithms for Molecular Response Functions: Resolvent Kernels, Time-Domain Sampling, Query Lower Bounds with Matched Single-Point Calibers, and a Six-Route Comparison
BibTeX
@misc{chen2026quantum,
title = {{Quantum Query Lower Bounds for Triangle-Listing and Spanners}},
author = {Yu Chen and Ananta Mukherjee and Mingyang Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37091},
eprint = {2609.37091},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37091},
}
RIS
TY - UNPB
TI - Quantum Query Lower Bounds for Triangle-Listing and Spanners
AU - Yu Chen
AU - Ananta Mukherjee
AU - Mingyang Yang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37091
UR - https://arxiv.org/abs/2609.37091
AB - This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of n-vertex graphs with Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n^3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥ 7, constructing a multiplicative k-spanner requires Ω(n^1+1/2μ_k) quantum queries, where μ_k=k/3+O(1). For k∈{7,8} the bound is Ω(n^5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large k the exponent 1+3/2k exceeds the 1+4/3k implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
ER -