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

References in corpus (1)

• Quantum lower bounds for the collision and the element distinctness problems

Cited by in corpus (7)

• Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
• Quantum Algorithms for the Triangle Problem
• Quantum algorithms for subset finding
• Applications of the Adversary Method in Quantum Query Algorithms
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• All Quantum Adversary Methods are Equivalent
• Quantum Algorithm for Commutativity Testing of a Matrix Set