Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

Background. Triangle finding is a graph-theoretic problem whose complexity is deeply connected to the complexity of several other computational tasks in theoretical computer science, such as solving path or matrix problems [3, 8, 9, 13, 18, 17, 19]. In its standard version (sometimes called unweighted triangle finding), it asks to find, given an undirected and unweighted graph G = (V,E), three vertices v1, v2, v3 ∈ V such that {v1, v2}, {v1, v3} and {v2, v3} are edges of the graph. Problems like triangle finding can be studied in the query complexity setting. In the usual model used to describe the query complexity of such problems, the set of edges E of the graph is unknown but can be accessed through an oracle: given two vertices u and v in V, one query to the oracle outputs one if {u, v} ∈ E and zero if {u, v} / ∈ E. In the quantum query complexity setting, one further assume that the oracle can be queried in superposition. Besides its intrinsic interest, the triangle finding problem has been one of the main problems that stimulated the development of new techniques in quantum query complexity, and the history of improvement of upper bounds on the query complexity of triangle finding parallels the development of general techniques in the quantum complexity setting, as we explain below. Grover search immediately gives, when applied to triangle finding as a search over the space of triples of vertices of the graph, a quantum algorithm with query complexity O(n3/2). Using amplitud