2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

段隆振 谢旭明 邱桃荣 杨舒晴

段隆振, 谢旭明, 邱桃荣, 杨舒晴. 基于量子计算的粗糙集核属性求解算法. 自动化学报, 2020, 46(8): 1753−1758 doi: 10.16383/j.aas.2018.c170328
引用本文: 段隆振, 谢旭明, 邱桃荣, 杨舒晴. 基于量子计算的粗糙集核属性求解算法. 自动化学报, 2020, 46(8): 1753−1758 doi: 10.16383/j.aas.2018.c170328
Duan Long-Zhen, Xie Xu-Ming, Qiu Tao-Rong, Yang Shu-Qing. A quantum algorithm of the computation of core in rough set. Acta Automatica Sinica, 2020, 46(8): 1753−1758 doi: 10.16383/j.aas.2018.c170328
Citation: Duan Long-Zhen, Xie Xu-Ming, Qiu Tao-Rong, Yang Shu-Qing. A quantum algorithm of the computation of core in rough set. Acta Automatica Sinica, 2020, 46(8): 1753−1758 doi: 10.16383/j.aas.2018.c170328

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

doi: 10.16383/j.aas.2018.c170328
基金项目: 

国家自然科学基金 61070139

国家自然科学基金 81460769

国家自然科学基金 61762045

江西省科技化项目 20112BBG70087

详细信息
    作者简介:

    段隆振   南昌大学教授.主要研究方向为数据挖掘, 并行计算与大数据. E-mail:lzhduan@126.com

    谢旭明   南昌大学博士研究生.主要研究方向为粗糙集与量子计算. E-mail: xiexuming@ncu.edu.cn

    杨舒晴   南昌大学博士研究生.主要研究方向为粗糙集与量子计算. E-mail:ysqsinuo@163.com

    通讯作者:

    邱桃荣   南昌大学教授.主要研究方向为粗糙集, 粒计算与量子计算.本文通信作者. E-mail: qiutaorong@ncu.edu.cn

A Quantum Algorithm of the Computation of Core in Rough Set

Funds: 

National Natural Science Foundation of China 61070139

National Natural Science Foundation of China 81460769

National Natural Science Foundation of China 61762045

Scientiflc and Technological Project of Jiangxi Province 20112BBG70087

More Information
    Author Bio:

    DUAN Long-Zhen    Professor at Nanchang University. His research interest covers data mining, parallel computing and big data

    XIE Xu-Ming    Ph. D. candidate at Nanchang University. His research interest covers rough set and quantum computing

    YANG Shu-Qing   Ph. D. candidate at Nanchang University. Her research interest covers rough set and quantum computing

    Corresponding author: QIU Tao-Rong   Professor at Nanchang University. His research interest covers rough set, granular computing and quantum computing. Corresponding author of this paper
  • 摘要: 粗糙集的核属性求解问题在经典计算中是一个NP问题.现有的方法中最优的时间复杂度也需要${\rm O}$$ \left(|C||U|\right)$($U$为论域、$C$为属性列数).由于量子计算的并行性特点, 本文致力于采用量子计算的方法来求解粗糙集的核属性, 拟提出了一种基于量子计算的粗糙集核属性求解算法.经过仿真实验, 在任何情况下, 该算法都能以1的总概率得到目标分量; 且通过理论分析证明了算法的时间复杂度不会高于${\rm O}$$\left(|\frac{{\rm{ \mathsf{ π}}}}{2\arcsin\sqrt {\frac{M}{C}}}+1||U|\right)$.
    Recommended by Associate Editor ZHANG Min-Ling
    1)  本文责任编委 张敏灵
  • 图  1  $G$算子内部结构

    Fig.  1  Inner structure of $G$

    图  2  Grover算法示意图

    Fig.  2  Diagram of Grover algorithm

    图  3  核属性个数与目标分量概率的关系

    Fig.  3  Comparing the number of core attributes and percentage of targets

    图  4  Comparing the number of core attributes and percentage of targets

    Fig.  4  Comparing the number of core attributes and the number of iterations

    表  1  UCI数据集实验结果

    Table  1  The test result of UCI sets

    数据集算法迭代次数概率
    Iris数据集Grover算法失效失效
    Iris数据集文献[15]算法20.9686
    Iris数据集文献[16]算法11.0000
    Iris数据集$\textbf{本文算法}$$\textbf{1}$$\textbf{1.0000}$
    Soybean数据集Grover算法10.8815
    Soybean数据集文献[15]算法30.9723
    Soybean数据集文献[16]算法20.9766
    Soybean数据集$\textbf{本文算法}$$\textbf{2}$$\textbf{1.0000}$
    Dermatology数据集Grover算法60.9983
    Dermatology数据集文献[15]算法121.0000
    Dermatology数据集文献[16]算法80.9978
    Dermatology数据集$\textbf{本文算法}$$\textbf{6}$$\textbf{1.0000}$
    Balloons数据集Grover算法失效失效
    Balloons数据集文献[15]算法20.9686
    Balloons数据集文献[16]算法11.0000
    Balloons数据集$\textbf{本文算法}$$\textbf{1}$$\textbf{1.0000}$
    Breast Cancer数据集Grover算法11.0000
    Breast Cancer数据集文献[15]算法30.9688
    Breast Cancer数据集文献[16]算法20.9451
    Breast Cancer数据集$\textbf{本文算法}$$\textbf{1}$$\textbf{1.0000}$
    下载: 导出CSV
  • [1] Pawlak Z. Rough sets. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356
    [2] 黎明, 张化光.基于粗糙集的神经网络建模方法研究.自动化学报, 2002, 28(1): 27-33 http://www.aas.net.cn/article/id/16371

    Li Ming, Zhang Hua-Guang. Research on the method of neural network modeling based on rough sets theory. Acta Automatica Sinica, 2002, 28(1): 27-33 http://www.aas.net.cn/article/id/16371
    [3] 张迎春, 郭禾.基于粗糙集和新能量公式的水平集图像分割.自动化学报, 2015, 41(11): 1913-1925 doi: 10.16383/j.aas.2015.c140823

    Zhang Ying-Chun, Guo He. Level set image segmentation based on rough set and new energy formula. Acta Automatica Sinica, 2015, 41(11): 1913-1925 doi: 10.16383/j.aas.2015.c140823
    [4] Hu X H, Cercone N. Learning in relational databases: A rough set approach. Computational Intelligence, 1995, 11(2): 323-338 doi: 10.1111/j.1467-8640.1995.tb00035.x
    [5] 叶东毅, 陈昭炯.一个新的差别矩阵及其求核方法.电子学报, 2002, 30(7): 1086-1088 doi: 10.3321/j.issn:0372-2112.2002.07.040

    Ye Dong-Yi, Chen Zhao-Jiong. A new discernibility matrix and the computation of a core. Acta Electronica Sinica, 2002, 30(7): 1086-1088 doi: 10.3321/j.issn:0372-2112.2002.07.040
    [6] 王国胤.决策表核属性的计算方法.计算机学报, 2003, 26(5): 611-615 doi: 10.3321/j.issn:0254-4164.2003.05.013

    Wang Guo-Yin. Calculation methods for core attributes of decision table. Chinese Journal of Computers, 2003, 26(5): 611-615 doi: 10.3321/j.issn:0254-4164.2003.05.013
    [7] 徐章艳, 杨炳儒, 蔡卫东, 崔巍, 谷冬元.一个基于正区域的快速求核算法.系统工程与电子技术, 2006, 28(12): 1902-1905, 1931 doi: 10.3321/j.issn:1001-506X.2006.12.032

    Xu Zhang-Yan, Yang Bing-Ru, Cai Wei-Dong, Cui Wei, Gu Dong-Yuan. Quick algorithm for computing core based on the positive region. Systems Engineering and Electronics, 2006, 28(12): 1902-1905, 1931 doi: 10.3321/j.issn:1001-506X.2006.12.032
    [8] 周江卫, 冯博琴, 刘洋.一种新的快速求核算法.西安交通大学学报, 2007, 41(6): 688-691 doi: 10.3321/j.issn:0253-987X.2007.06.013

    Zhou Jiang-Wei, Feng Bo-Qin, Liu Yang. New algorithm for quick computing core. Journal of Xi'an Jiaotong University, 2007, 41(6): 688-691 doi: 10.3321/j.issn:0253-987X.2007.06.013
    [9] 尹林子, 阳春华, 王晓丽, 桂卫华.基于标记可辨识矩阵的增量式属性约简算法.自动化学报, 2014, 40(3): 397-404 doi: 10.3724/SP.J.1004.2014.00397

    Yin Lin-Zi, Yang Chun-Hua, Wang Xiao-Li, Gui Wei-Hua. An incremental algorithm for attribute reduction based on labeled discernibility matrix. Acta Automatica Sinica, 2014, 40(3): 397-404 doi: 10.3724/SP.J.1004.2014.00397
    [10] 张靖, 李春文, 吴热冰.开放环境下多比特量子计算机的相干控制模型.自动化学报, 2005, 31(5): 759-764 http://www.aas.net.cn/article/id/15967

    Zhang Jing, Li Chun-Wen, Wu Re-Bing. Coherent control modeling of quantum computers in open environments. Acta Automatica Sinica, 2005, 31(5): 759-764 http://www.aas.net.cn/article/id/15967
    [11] Deutsch D. Quantum theory, the church-turing principle and the universal quantum computer. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 1985, 400(1818): 97-117
    [12] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997, 26(5): 1484-1509 doi: 10.1137/S0097539795293172
    [13] Grover L. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. New York, USA: IEEE, 1996. 212-219
    [14] 孙国栋, 苏胜辉, 徐茂智.求根问题的量子计算算法.北京工业大学学报, 2015, 41(3): 366-371 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=bjgydxxb201503007

    Sun Guo-Dong, Su Sheng-Hui, Xu Mao-Zhi. Quantum mechanical algorithms for solving root finding problem. Journal of Beijing University of Technology, 2015, 41(3): 366-371 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=bjgydxxb201503007
    [15] Tulsi T, Grover L K, Patel A. A new algorithm for fixed point quantum search. Quantum Information & Computation, 2006, 6(6): 483-494 http://www.researchgate.net/publication/2195367_A_new_algorithm_for_fixed_point_quantum_search
    [16] 张煜东, 韦耿, 吴乐南.一种改进的Grover量子搜索算法.信号处理, 2009, 25(2): 256-259 doi: 10.3969/j.issn.1003-0530.2009.02.017

    Zhang Yu-Dong, Wei Geng, Wu Le-Nan. An improved Grover quantum searching algorithm. Signal Processing, 2009, 25(2): 256-259 doi: 10.3969/j.issn.1003-0530.2009.02.017
    [17] 李盼池, 李士勇.基于自适应相位旋转的Grover量子搜索算法.系统仿真学报, 2009, 21(12): 3557-3560 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtfzxb200912014

    Li Pan-Chi, Li Shi-Yong. Grover$'$s quantum search algorithm based on adaptive phase rotation. Journal of System Simulation, 2009, 21(12): 3557-3560 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtfzxb200912014
    [18] 朱皖宁, 陈汉武.迭代次数自适应的Grover算法.电子学报, 2016, 44(12): 2975-2980 doi: 10.3969/j.issn.0372-2112.2016.12.023

    Zhu Wan-Ning, Chen Han-Wu. Grover auto-control searching algorithm. Acta Electronica Sinica, 2016, 44(12): 2975-2980 doi: 10.3969/j.issn.0372-2112.2016.12.023
    [19] Brassard C H, Hoyer P, Tapp A. Quantum counting. In: Proceedings of the 25th International Colloquium Automata Language and Programming. Berlin, Germany: Springer-Verlag, 1998. 820-831
  • 加载中
图(4) / 表(1)
计量
  • 文章访问数:  1170
  • HTML全文浏览量:  185
  • PDF下载量:  96
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-06-16
  • 录用日期:  2018-01-01
  • 刊出日期:  2020-08-26

目录

    /

    返回文章
    返回