Quantum query complexity of triangle finding

How many questions of the form "is $\{u,v\}$ an edge?" must a quantum algorithm ask to find a triangle in an $n$-vertex graph? Classical algorithms need about $n^2$ such queries, and the best quantum algorithm uses $O(n^{5/4})$, but the best lower bound is only $\Omega(n)$. Triangle finding has driven the development of quantum walks and learning graphs, and closing this gap is a basic open problem in quantum query complexity.

Problem

Let $G$ be a simple graph on the vertex set $\{1,\dots,n\}$ with adjacency matrix $A$. A quantum algorithm may access $A$ only through the oracle

$$O_A\lvert u,v,z\rangle=\lvert u,v,z\oplus A_{uv}\rangle ,$$

which it can query in superposition. It must output three vertices $u,v,w$ with $A_{uv}=A_{vw}=A_{wu}=1$ if a triangle exists, and report that $G$ is triangle-free otherwise, with success probability at least $2/3$ on every graph. Let $Q_\triangle(n)$ be the least number of queries such an algorithm needs on $n$-vertex graphs. It is known that

$$\Omega(n)\le Q_\triangle(n)\le O(n^{5/4}).$$

Question. Determine the growth of $Q_\triangle(n)$. In particular, is there an algorithm with $O(n^{5/4-\varepsilon})$ queries, or a lower bound $\Omega(n^{1+\varepsilon})$, for some constant $\varepsilon>0$?

Background

The quantum query complexity of triangle finding was first raised by Buhrman, Dürr, Heiligman, Høyer, Magniez, Santha and de Wolf, whose algorithm uses $O(n+\sqrt{nm})$ queries on graphs with $m$ edges [1, 2]. Grover search alone gives $O(n^{3/2})$ queries, while classical randomized algorithms need $\Theta(n^2)$ [4]. The upper bound then fell with each new technique: $\tilde O(n^{13/10})$ with quantum walks (Magniez, Santha and Szegedy), $O(n^{35/27})$ with learning graphs (Belovs), and $O(n^{9/7})$ (Lee, Magniez and Santha) [2, 4]. The problem is also closely tied to matrix multiplication [2].

What is known

• Upper bound $O(n^{5/4})$: Le Gall's $\tilde O(n^{5/4})$-query algorithm (2014) exploits combinatorial properties of unweighted graphs [4], and Carette, Laurière and Magniez removed the logarithmic factors with extended learning graphs (2017) [5].
• Lower bound $\Omega(n)$: this trivial bound is the best known [4]. Magniez, Santha and Szegedy observed that the adversary methods available in 2005 cannot prove more for this problem, because a triangle is a certificate of constant size [2].
• For an edge-weighted version, the triangle-sum problem, Belovs and Rosmanis proved a lower bound of $\Omega(n^{9/7}/\sqrt{\log n})$ queries [3]. Non-adaptive learning graphs cannot tell the two versions apart, so for unweighted graphs they cannot beat $n^{9/7}$ by more than a $\sqrt{\log n}$ factor; the $n^{5/4}$ algorithms get around this by using the structure of unweighted graphs, showing that unweighted triangle finding is the easier problem [3, 4].

What would count as progress

• An algorithm with $O(n^{5/4-\varepsilon})$ queries for a constant $\varepsilon>0$. Algorithms in the learning-graph frameworks of [3, 5] come with explicit complexity formulas that can be checked directly.
• A lower bound $\Omega(n^{1+\varepsilon})$ for unweighted triangle finding. The general adversary bound characterizes quantum query complexity [4], so such a bound can in principle be certified by an explicit adversary matrix; it must go beyond the methods discussed in [2].

References

1. H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha and R. de Wolf, "Quantum algorithms for element distinctness", SIAM Journal on Computing 34(6), 1324–1330 (2005). doi:10.1137/S0097539702402780
2. F. Magniez, M. Santha and M. Szegedy, "Quantum algorithms for the triangle problem", SIAM Journal on Computing 37(2), 413–424 (2007). doi:10.1137/050643684
3. A. Belovs and A. Rosmanis, "On the power of non-adaptive learning graphs", Computational Complexity 23, 323–354 (2014). doi:10.1007/s00037-014-0084-1
4. F. 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:10.1109/FOCS.2014.31
5. T. Carette, M. Laurière and F. Magniez, "Extended learning graphs for triangle finding", in 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), LIPIcs 66, 20 (2017). doi:10.4230/LIPIcs.STACS.2017.20

Source

Imported from QIQCOP Zoo op_0c17d9fef967858d, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.