{"id":"arxiv/2611.06751","url":"https://arxiv.org/abs/2611.06751","tags":["quant-ph","cs.DS"],"score":0,"title":"A Quantum Lower Bound for Triangle Finding","domain":"quant-ph","source":"arxiv","authors":["Arjan Cornelissen","Amin Shiraz Gilani","Xingyu Zhou"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}