A Quantum Lower Bound for Triangle Finding
Abstract
Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For N-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from O(N3/2) to O(N5/4). However, the best known lower bound has remained the elementary Ω(N) bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that Ω(N13/12) queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.
Related
- A quantum lower bound for path finding in welded trees
- Quantum Query Lower Bounds for Triangle-Listing and Spanners
- Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Improved lower bound for the two-way-assisted quantum capacity of the bosonic thermal-loss channel
BibTeX
@misc{cornelissen2026quantum,
title = {{A Quantum Lower Bound for Triangle Finding}},
author = {Arjan Cornelissen and Amin Shiraz Gilani and Xingyu Zhou},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06751},
eprint = {2611.06751},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06751},
}
RIS
TY - UNPB
TI - A Quantum Lower Bound for Triangle Finding
AU - Arjan Cornelissen
AU - Amin Shiraz Gilani
AU - Xingyu Zhou
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06751
UR - https://arxiv.org/abs/2611.06751
AB - Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For N-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from O(N^3/2) to O(N^5/4). However, the best known lower bound has remained the elementary Ω(N) bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that Ω(N^13/12) queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.
ER -