摘要
为提高经典k-means算法的计算效率,引入量子计算理论得到量子k-means算法。先将聚类数据和k个聚类中心制备成量子态,并行计算其相似度,接着利用相位估计算法将相似度信息保存到量子比特中,然后利用最小值查找量子算法查找最相似的聚类中心点。对比两种算法的复杂度可知,在一定条件下,相对经典算法而言,量子k-means算法的时间复杂度降低,空间复杂度得到指数级降低。
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.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2018年第2期539-544,共6页
Journal of Jilin University:Engineering and Technology Edition
基金
国家自然科学基金项目(61571226)
江苏省自然科学基金项目(BK20140823)
关键词
人工智能
聚类
量子计算
量子算法
量子k-means
artificial intelligence
clustering
quantum computation
quantum algorithm
quantum k-means
