Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9 / 7). This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012) making O(n35 / 27) queries. For the problem of determining if an operation ∘ : S× S→ S is associative, we give an algorithm making O(| S| 10 / 7) queries, the first improvement to the trivial O(| S| 3 / 2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm