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

A Quantum Algorithm of the Computation of Core in Rough Set

粗糙集的核属性求解问题在经典计算中是一个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.