Computer Science ›› 2016, Vol. 43 ›› Issue (3): 80-83.doi: 10.11896/j.issn.1002-137X.2016.03.016

Previous Articles     Next Articles

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!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .