Publication Date:
2015-10-27
Description:
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 (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012 ) making \(O(n^{35/27})\) queries. For the problem of determining if an operation \(\circ : S \times S \rightarrow 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.
Print ISSN:
0178-4617
Electronic ISSN:
1432-0541
Topics:
Computer Science
,
Mathematics
