Quantum query complexity of Triangle Finding

Problem

What is the bounded-error quantum query complexity of finding a triangle in an \(n\)-vertex graph given oracle access to its adjacency matrix?

Let \(G=(V,E)\) be a simple undirected graph with \(V=[n]\), and let \(A\in\{0,1\}^{n\times n}\) be its adjacency matrix. The input is accessed through a quantum oracle acting as

\begin{equation} O_A\lvert u,v,z\rangle =\lvert u,v,z\oplus A_{uv}\rangle . \tag{1} \end{equation}

The task is to output three distinct vertices \(u,v,w\in[n]\) satisfying

\begin{equation} A_{uv}=A_{vw}=A_{wu}=1, \tag{2} \end{equation}

if such vertices exist, and otherwise report that the graph is triangle-free. Let \(Q_{\triangle}(n)\) denote the minimum number of queries to the oracle in (1) required by a bounded-error quantum algorithm for this task.

The best known general bounds are

\begin{equation} Q_{\triangle}(n)=O\left(n^{5/4}\right) \qquad\text{and}\qquad Q_{\triangle}(n)=\Omega(n). \tag{3} \end{equation}

The open question is to determine the asymptotic behavior of \(Q_{\triangle}(n)\), equivalently to improve either the upper or lower bound in (3) until the bounds match.

Source

Li and Li explicitly identify the gap between the \(O(n^{5/4})\) upper bound and the \(\Omega(n)\) lower bound as open for the ordinary adjacency-matrix problem [LL25]. The precise statement above is contributor wording that packages this known gap as a standalone open problem; it is not a verbatim question attributed to Li and Li or to the authors of the earlier algorithms.

Progress

Le Gall obtained a bounded-error quantum algorithm with query complexity \(\widetilde O(n^{5/4})\), using combinatorial properties specific to unweighted triangle finding together with quantum-search and quantum-walk techniques [LG14].
Carette, Laurière, and Magniez introduced extended learning graphs, removing the polylogarithmic overhead from the above bound and establishing the current best general upper bound \(O(n^{5/4})\); their framework also yields improved bounds in several sparse-graph regimes [CLM17].
Belovs and Rosmanis proved an \(\Omega(n^{9/7}/\sqrt{\log n})\) quantum query lower bound for the related edge-weighted triangle-sum problem and showed that the \(O(n^{9/7})\) non-adaptive learning-graph approach to Triangle Finding is essentially optimal within that framework [BR14].

Comment

The open question is to determine the asymptotic behavior of \(Q_{\triangle}(n)\): either an algorithm using \(O(n^{5/4-\varepsilon})\) queries for some constant \(\varepsilon>0\), or a lower bound of \(\Omega(n^{1+\varepsilon})\) for unrestricted bounded-error quantum algorithms; neither is known for general unweighted graphs in the adjacency-matrix oracle model. The distinction between unweighted Triangle Finding and edge-weighted Triangle Sum is essential: the stronger lower bounds known for Triangle Sum (Progress above) must not be recorded as lower bounds for this problem. Li and Li, who identify the gap as open, study a different question, namely derandomizing related triangle-finding algorithms under an additional uniqueness promise, and do not close this gap [LL25].

References

[LG14]: François Le Gall, “Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), 216–225 (2014).DOI arXiv
[CLM17]: Titouan Carette, Mathieu Laurière, and Frédéric Magniez, “Extended Learning Graphs for Triangle Finding,” in 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), LIPIcs 66, Article 20 (2017).DOI arXiv
[BR14]: Aleksandrs Belovs and Ansis Rosmanis, “On the Power of Non-Adaptive Learning Graphs,” Computational Complexity 23, 323–354 (2014).DOI arXiv
[LL25]: Guanzhong Li and Lvzhou Li, “Derandomization of Quantum Algorithm for Triangle Finding,” Information and Computation 304, 105295 (2025).DOI arXiv

Quantum query complexity of Triangle Finding

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems