计算机科学 ›› 2016, Vol. 43 ›› Issue (3): 80-83.doi: 10.11896/j.issn.1002-137X.2016.03.016

• 第十五届中国机器学习会议 • 上一篇    下一篇

基于一维三态量子游走的量子聚类算法

徐永振,郭躬德,蔡彬彬,林崧   

  1. 福建师范大学数学与计算机科学学院 福州350007福建师范大学网络安全与密码技术福建省高校重点实验室 福州350007,福建师范大学数学与计算机科学学院 福州350007福建师范大学网络安全与密码技术福建省高校重点实验室 福州350007,福建师范大学数学与计算机科学学院 福州350007福建师范大学网络安全与密码技术福建省高校重点实验室 福州350007,福建师范大学数学与计算机科学学院 福州350007福建师范大学网络安全与密码技术福建省高校重点实验室 福州350007
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金项目(61202451),福建省教育厅重点项目(JA12062)资助

Quantum Clustering Algorithm Based on One-dimensional Three-state Quantum Walk

XU Yong-zhen, GUO Gong-de, CAI Bin-bin and LIN Song   

  • Online:2018-12-01 Published:2018-12-01

摘要: 量子游走具有与经典随机游走不同的特性,因此它已经被用来解决包括元素区分、组合优化、图同构等问题。考虑量子游走和聚类两个领域,提出了一个基于一维三态离散量子游走的聚类算法。在该算法中,将数据点看作游走粒子;然后,这些粒子执行三态量子游走,接着根据粒子的测量结果更新数据点的属性值;最后,属于同一簇的数据点将会聚集,而属于不同簇的数据点将会分离。仿真实验结果表明了所提算法的有效性。

关键词: 量子游走,无监督学习,数据聚类,量子计算

Abstract: As compared to classical random walk,quantum walk exhibits some remarkably different features.Thus,it has been exploited to solve some kinds of problems,e.g.element distinctness,combinatorial optimization,graph mat-ching problem and so on.Considering the two related research fields of quantum walks and data cluster analysis,a quantum clustering algorithm based on the one-dimensional three-state quantum walk was proposed.In this algorithm,each data point is regarded as one particle.Then,these particles perform the three-state quantum walk.After that,according to the measurement results,the attribute values of the corresponding data points are updated.At last,the data points belonging to the same group will gather together,while those belonging to different group will be separated.The simulation results demonstrate that the proposed algorithm is effective.

Key words: Quantum walk,Unsupervised learning,Data clustering,Quantum computation

[1] Shor P W.Algorithms for quantum computation:Discrete lo-garithms and factoring[C]∥Proceedings of 35th Annual Sympo-sium on Foundations of Computer Science,1994.IEEE,1994:124-134
[2] Grover L K.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325-328
[3] Farhi E,Goldstone J,Gutmann S,et al.A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem [J].Science,2001,292(5516):472-475
[4] Fayyad U,Piatetsky-Shapiro G,Smyth P.From data mining to knowledge discovery in databases[J].AI magazine,1996,17(3):37-54
[5] SchuldM,Sinayskiy I,et al.An introduction to quantum machine learning[J].Contemporary Physics,2015,6(2):172-185
[6] Wang S H,Long G L.Big data and quantum computation[J].Chinese Science Bulletin,2015,60(5/6):499-508(in Chinese) 王书浩,龙桂鲁.大数据与量子计算[J].科学通报(中文版),2015,0(5/6):499-508
[7] Venegas-Andraca S E.Quantum walks:a comprehensive review[J].Quantum Information Processing,2012,11(5):1015-1106
[8] Childs A M.Universal computation by quantum walk[J].Physical Review Letters,2009,102(18):180501
[9] Li Q,He Y,Jiang J.A hybrid classical-quantum clustering algorithm based on quantum walks[J].Quantum Information Processing,2011,10(1):13-26
[10] Inui N,Konno N,Segawa E.One-dimensional three-state quantum walk[J].Physical Review E,2005,72(5):056112
[11] Erkan G.Language model-based document clustering using random walks[C]∥Proceedings of the main conference on human language technology conference of the north American chapter of the association of computational linguistics.Association for Computational Linguistics,2006:479-486
[12] MacQueen J.Some methods for classification and analysis ofmultivariate observations[J].Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability,1967,1(14):281-297

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .