Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frederic Magniez, Miklos Santha

We show that the quantum query complexity of detecting if an $n$-vertex graph contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm of Belovs making $O(n^{…