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


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!