基于量子计算的粗糙集核属性求解算法  

A Quantum Algorithm of the Computation of Core in Rough Set

作　　者：段隆振[1] 谢旭明 邱桃荣[1] 杨舒晴[1] DUAN Long-Zhen;XIE Xu-Ming;QIU Tao-Rong;YANG Shu-Qing(College of Information Engineering,Nanchang University,Nanchang 330031;Library of Nanchang University,Nanchang 330031)

机构地区：[1]南昌大学信息工程学院,南昌330031 [2]南昌大学图书馆,南昌330031

出　　处：《自动化学报》2020年第8期1753-1758,共6页Acta Automatica Sinica

基　　金：国家自然科学基金(61070139,81460769,61762045);江西省科技化项目(20112BBG70087)资助。

摘　　要：粗糙集的核属性求解问题在经典计算中是一个NP问题.现有的方法中最优的时间复杂度也需要O(|C||U|)(U为论域、C为属性列数).由于量子计算的并行性特点,本文致力于采用量子计算的方法来求解粗糙集的核属性,拟提出了一种基于量子计算的粗糙集核属性求解算法.经过仿真实验,在任何情况下,该算法都能以1的总概率得到目标分量;且通过理论分析证明了算法的时间复杂度不会高于O(|π/2arcsin√M/C+1||U|).The computation of core in rough set is an NP-hard problem in classic computing.The best time complexity of the existing algorithms is O(|C||U|)(U stands for Universe,C stands for the number of attributes).Due to its ability to compute in parallel,quantum computing,is adopted to find the core in rough set in this research.Thus,a quantum algorithm of the computation of core in rough set is proposed.Based on sim-ulation experiment,the proposed algorithm is able to get one target out of the target set with the probability of 1.And the time complexity of the new algorithm is proved to be no more than O(|π/2arcsin√M/C+1||U|)by theoretical analysis.

关 键 词：量子计算 粗糙集 核属性 算法设计 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]