计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (14): 57-61.DOI: 10.3778/j.issn.1002-8331.1906-0272

• 理论与研发 • 上一篇    下一篇

改进量子搜索算法及其在核属性求解上的应用

谢旭明,段隆振,邱桃荣,杨幼凤   

  1. 南昌大学 信息工程学院,南昌 330031
  • 出版日期:2020-07-15 发布日期:2020-07-14

Improved Quantum Search Algorithm and Its Application on Computation of Core

XIE Xuming, DUAN Longzhen, QIU Taorong, YANG Youfeng   

  1. College of Information Technology, Nanchang University, Nanchang 330031, China
  • Online:2020-07-15 Published:2020-07-14

摘要:

大部分的量子算法都必须先求解目标分量占比,否则算法的迭代次数无法确定。迭代次数自适应Grover算法有效地避开了目标分量占比求解这个步骤,但其性能相对于Grover算法来说并没有任何改善。致力于提升迭代次数自适应Grover算法的性能,提出了一种改进量子搜索算法,并将其应用于求解粗糙集的核属性。经过仿真实验,改进算法不仅实现了迭代次数自适应,而且整体上提升了获得目标分量的概率,使得获得目标分量的概率恒高于85%。

关键词: 量子搜索, 自适应, 粗糙集, 核属性, 算法设计

Abstract:

The ratio of targets is significant, basically for most of quantum search algorithms, and these algorithms cannot be successfully implemented without knowing the ratio of targets beforehand. While, Grover auto-control searching algorithm avoids this problem effectively, but the drawback of this algorithm is that it has no improvement over the Grover quantum search on behalf of final success probability. Dedicated to solve the aforesaid problem, an improved algorithm is proposed, and also applied in the computation of core of rough sets, in this study. Based on simulative experiment, not only does the proposed algorithm iterate self-adaptively, but it also has an overall improvement on the success probability, which is constantly over 85%.

Key words: quantum search, self-adaptive, rough set, core, algorithm design