吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (2): 539-544.doi: 10.13229/j.cnki.jdxbgxb20170051

Previous Articles     Next Articles

Quantum k-means algorithm

LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia   

  1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • Received:2017-01-14 Online:2018-03-01 Published:2018-03-01

RICH HTML

0   

PDF (PC)

5139

Abstract: In this paper a quantum k-means algorithm is proposed by integrating the quantum paradigm to improve the efficiency of traditional k-means algorithm. First, each vector and k cluster centers are prepared to be in quantum superposition, which are then utilized to compute the similarities in parallel. Second, the quantum amplitude estimation algorithm is applied to convert the similarities into quantum bit. Finally, from the quantum bit the most similar center of the vector is obtained using the quantum algorithm for determining the minimum. Theoretical analysis shows that, compared with the traditional quantum algorithm, the time complexity of the quantum k-means algorithm decreases under given condition and the space complexity diminishes exponentially.

Key words: artificial intelligence, clustering, quantum computation, quantum algorithm, quantum k-means

CLC Number: 

  • TP387
[1] 王书浩, 龙桂鲁. 大数据与量子计算[J].科学通报, 2015,60 (5): 499-508.
Wang Shu-hao, Long Gui-lu. Big data and quantum computation[J]. Chin Sci Bull, 2015, 60(5):499-508.
[2] Anguita D, Ridella S, Rivieccio F, et al. Quantum optimization for training support vector machines[J]. Neural Networks, 2003, 16(5/6): 763-770.
[3] Grover L K. A fast quantum mechanical algorithm for database search[C] ∥Proc 28th Ann ACM Symp Theory of Computing, New York, USA,1996:212-219.
[4] Rebentrost P, Mohseni M, Lloyd S. Quantum support vector machine for big data classification[J]. Physical Review Letters, 2014, 113(13): 130503.
[5] Lu S,Braunstein S L. Quantum decision tree classifier[J]. Quantum Information Processing, 2014, 13(3): 757-770.
[6] 阮越, 陈汉武, 刘志昊, 等. 量子主成分分析算法[J]. 计算机学报, 2014, 37(3): 666-676.
Ruan Yue, Chen Han-wu, Liu Zhi-hao, et al. Quantum principal component analysis algorithm[J]. Chinese Journal of Computers, 2014,37(3):666-676.
[7] 徐永振, 郭躬德, 蔡彬彬, 等. 基于一维三态量子游走的量子聚类算法[J]. 计算机科学, 2016, 43(3): 80-83.
Xu Yong-zhen, Guo Gong-de, Cai Bin-bin, et al. Quantum clustering algorithm based on one-dimensional three-state quantum walk[J]. Computer Science, 2016, 43(3): 80-83.
[8] Elhaddad M E, Mohammed S A O. Analysing the impact of quantum computing using system dynamics[C]∥Engineering & MIS (ICEMIS), IEEE, 2016: 1-5.
[9] Jain A K,Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys (CSUR), 1999, 31(3): 264-323.
[10] 许美慧,尹建芹,张玲,等. 可处理暗腔的日冕物质抛射检测新方法[J]. 光学精密工程, 2016, 24(10s):591-599.
Xu Mei-hui, Yin Jian-qin, Zhang Ling, et al. New detection method for coronal mass ejection capable of dark cavity processing[J]. Optics and Precision Engineering, 2016, 24(10s): 591-599.
[11] 王丽. 融合底层和中层字典特征的行人重识别[J]. 中国光学, 2016, 9(5): 540-546.
Wang Li. Pedestrian re-identification based on fusing low-level and mid-level features[J]. Chinese Optics, 2016, 9(5): 540-546.
[12] Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1):1-37.
[13] 秦大同, 詹森,漆正刚,等. 基于 K-均值聚类算法的行驶工况构建方法[J].吉林大学学报:工学版,2016,46(2):383-389.
Qin Da-tong, Zhan Sen, Qi Zheng-gang, et al. Driving cycle construction using K-means clustering method[J]. Journal of Jilin University(Engineering and Technology Edition),2016 ,46(2): 383-389.
[14] 赵文昌, 李忠木. 融合改进人工蜂群和K均值聚类的图像分割[J]. 液晶与显示, 2017,32(9):726-735.
Zhao Wen-chang, Li Zhong-mu. Image segmentation algorithm based on improved artificial bee colony and K-mean clustering[J]. Chinese Journal of Liquid Crystals and Displays, 2017, 32(9): 726-735.
[15] 丁有伟, 秦小麟, 刘亮, 等. 一种异构集群中能量高效的大数据处理算法[J]. 计算机研究与发展, 2015, 52(2): 377-390.
Ding You-wei, Qin Xiao-lin, Liu Liang, et al. An energy efficient algorithm for big data processing in heterogeneous cluster[J]. Journal of Computer Research and Development, 2015, 52(2): 377-390.
[16] Forrest W. How to cut datacentre carbon emissions? [EB/OL].[2014-12-08].http∥www.computerweekly.com/Articles/2008/12/05/233748/how-tocut-data-centre carbon-emissions.htm
[17] Aïmeur E, Brassard G, Gambs S. Machine learning in a quantum world[J]. Advances in Artificial Intelligence,2006,4013:431-442.
[18] Aïmeur E, Brassard G, Gambs S. Quantum clustering algorithms[C]∥Proceedings of the 24th International Conference on Machine Learning, 2007: 1-8.
[19] Aïmeur E, Brassard G, Gambs S. Quantum speed-up for unsupervised learning[J]. Machine Learning, 2013, 90(2):261-287.
[20] Lloyd S, Mohseni M, Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning[J]. arXiv, 2013:1307.0411.
[21] Brassard G, Hoyer P,Mosca M, et al. Quantum amplitude amplification and estimation[J]. Contemporary Mathematics, 2002, 305: 53-74.
[22] Durr C, Hoyer P. A quantum algorithm for finding the minimum[J/OL]. [2016-07-11].https://arxiv.org/abs/quant-ph/9607014.
[23] 李强,蒋静坪.量子K最近邻算法[J].系统工程与电子技术,2008,30(5):940-943.
Li Qiang, Jiang Jing-ping. Quantum K nearest neighbor algorithm[J]. Systems Engineering and Electronics, 2008,30(5):940-943.
[24] 陈汉武,高越,张军.量子K-近邻算法[J].东南大学学报:自然科学版, 2015, 45(4):647-651.
Chen Han-wu, Gao Yue, Zhang Jun. Quantum K-nearest neighbor algorithm[J]. Journal of Southeast University(Natural Science Edition), 2015,45(4):647-651.
[1] LIU Zhong-min,WANG Yang,LI Zhan-ming,HU Wen-jin. Image segmentation algorithm based on SLIC and fast nearest neighbor region merging [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1931-1937.
[2] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[3] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[4] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[5] ZHANG Man, SHI Shu-ming. Analysis of state transition characteristics for typical vehicle driving cycles [J]. 吉林大学学报(工学版), 2018, 48(4): 1008-1015.
[6] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[7] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[8] DONG Ying, CUI Meng-yao, WU Hao, WANG Yu-hou. Clustering wireless rechargeable sensor networks charging schedule based on energy prediction [J]. 吉林大学学报(工学版), 2018, 48(4): 1265-1273.
[9] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[10] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[11] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[12] DENG Jian-xun, XIONG Zhong-yang, DENG Xin. Improved DNALA algorithm based on spectral clustering matrix [J]. 吉林大学学报(工学版), 2018, 48(3): 903-908.
[13] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[14] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[15] HOU Xian-yao, CHEN Xue-wu. Use of public transit information market segmentation based onattitudinal factors [J]. 吉林大学学报(工学版), 2018, 48(1): 98-104.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Guang-jie,XU Tao,LI Jun-lou,YU Zheng-lei,XIU Hang,CHENG Fei. Design and optimization of double chamber model of gas turbine transition piece[J]. 吉林大学学报(工学版), 2014, 44(5): 1360 -1365 .
[2] CHU Liang, SUN Cheng-wei, GUO Jian-hua, ZHAO Di, LI Wen-hui. Evaluation method of braking energy recovery based on wheel cylinder pressure[J]. 吉林大学学报(工学版), 2018, 48(2): 349 -354 .
[3] LI Jing, DING Ming-hui, LI Li-gang, CHEN Li-jun. Dynamic characteristics analysis and optimization of air spring based on the piston shape[J]. 吉林大学学报(工学版), 2018, 48(2): 355 -363 .
[4] SHI Wen-ku, LIU Guo-zheng, SONG Hai-sheng, CHEN Zhi-yong, ZHANG Bao. Vibration and noise characteristics of electric bus[J]. 吉林大学学报(工学版), 2018, 48(2): 373 -379 .
[5] QIN Da-tong, LIN Yu-pei, HU Jian-jun, GUO Zi-han. Regenerative braking control strategy of plug-in hybrid electric vehicle based on speed ratio control continuously variable transmission[J]. 吉林大学学报(工学版), 2018, 48(2): 380 -386 .
[6] JIAO Yu-ling, XU Liang-cheng, WANG Zhan-zhong, ZHANG Peng. Balance experiment and analysis of double U-shaped assembly line based on directed network[J]. 吉林大学学报(工学版), 2018, 48(2): 454 -459 .
[7] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework[J]. 吉林大学学报(工学版), 2018, 48(2): 533 -538 .
[8] LIU Zhou-zhou, PENG Han. Topology control algorithm based on node reliability in WSN[J]. 吉林大学学报(工学版), 2018, 48(2): 571 -577 .
[9] XIE Zhi-qiang, GUO He, SU Wen-xiu, XIN Yu, YANG Jing. Reversal sequence integrated scheduling algorithm of multiple workshop with multi-procedures ended together[J]. 吉林大学学报(工学版), 2018, 48(2): 578 -587 .
[10] WANG Ke, LIU Fu, KANG Bing, HUO Tong-tong, ZHOU Qiu-zhan. Bionic hypocenter localization method inspired by sand scorpion in locating preys[J]. 吉林大学学报(工学版), 2018, 48(2): 633 -639 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd