Quantum Algorithms for the Triangle Problem

Abstract

We present two new quantum algorithms that either find a triangle (a copy of $K_{3}$) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes $\tilde{O}(n^{10/7})$ queries. The second algorithm uses $\tilde{O}(n^{13/10})$ queries and is based on a design concept of Ambainis [in Proceedings of the $45$th IEEE Symposium on Foundations of Computer Science, 2004, pp. 22–31] that incorporates the benefits of quantum walks into Grover Search [L. Grover, in Proceedings of the Twenty‐Eighth ACM Symposium on Theory of Computing, 1996, pp. 212–219]. The first algorithm uses only $O(\log n)$ qubits in its quantum subroutines, whereas the second one uses $O(n)$ qubits. The Triangle Problem was first treated in [H. Buhrman et al., SIAM J. Comput., 34 (2005), pp. 1324–1330], where an algorithm with $O(n+\sqrt{nm})$ query complexity was presented, where m is the number of edges of G.