On the Quantum Query Complexity of Detecting Triangles in Graphs

Abstract

We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on $n$ nodes can be done using $O(n^{1+\frac{3}{7}}{\log }^{2}n)$ quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of $O(n^{1+\frac{1}{2}})$.

13 pages

Cited by in corpus (3)

• Quantum Algorithms for the Triangle Problem
• All Quantum Adversary Methods are Equivalent
• Quantum Algorithm for Commutativity Testing of a Matrix Set