An $O(n^{1.3})$ Quantum Algorithm for the Triangle Problem
Frédéric Magniez, Miklós Sántha, Márió Szegedy · arXiv (Cornell University) · 2003
We present a new quantum algorithm that either finds a triangle (a copy of K3) in an undirected graph G on n nodes, or it outputs “reject ” if G is triangle free. The algorithm uses O(n 1.3) queries, and it is based on a new design concept of Ambainis [Amb03] that incorporates the benefits of quantum walks into Grover search [Gro96]. The algorithm both improves on, and is simpler than a recent algorithm of Szegedy [Sze03] which has Õ(n10/7) query complexity. The Triangle Problem was first treated in [BDH + 01], where an algorithm with O ( √ n|E|) query complexity was presented (here |E | is the number of edges of G). 1