Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing
详细信息 查看全文
- 作者：Troy Lee ; Frédéric Magniez ; Miklos Santha
- 关键词：Quantum algorithms ; Query complexity ; Learning graphs ; Triangle testing ; Associativity testing
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：77
- 期：2
- 页码：459-486
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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.