Please use this identifier to cite or link to this item:
Title: Improved quantum query algorithms for triangle finding and associativity testing
Authors: Lee, T.
Magniez, F.
Santha, M. 
Issue Date: 2013
Citation: Lee, T.,Magniez, F.,Santha, M. (2013). Improved quantum query algorithms for triangle finding and associativity testing. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 1486-1502. ScholarBank@NUS Repository.
Abstract: 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 [2] making O(n35/27) queries. For the problem of determining if an operation o:S x S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|5|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. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms. Copyright © SIAM.
Source Title: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN: 9781611972511
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Jan 18, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.