首页> 外文期刊>Algorithmica >Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing
【24h】

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 . This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77-84, 2012) making queries. For the problem of determining if an operation is associative, we give an algorithm making queries, the first improvement to the trivial 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.
机译:我们证明了检测n个顶点图是否包含三角形的量子查询复杂度为。这改进了Belovs以前最好的算法(第44届计算机理论研讨会论文集,第77-84页,2012年)进行查询。对于确定某个操作是否具有关联性的问题,我们提供了一种进行查询的算法,这是对Grover搜索的简单应用的首次改进。我们的算法是使用Belovs的学习图框架设计的。我们提供了一系列用于检测恒定大小的子图的算法,这些子图可能是有方向的和有颜色的。这些算法是用一种简单的高级语言设计的。我们的主要定理说明了如何将此高级语言编译为学习图并给出最终的复杂性。我们进行改进的关键思想是允许算法保留更多的数据库参数自由度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号