计算机科学 ›› 2023, Vol. 50 ›› Issue (8): 27-36.doi: 10.11896/jsjkx.220600124

• 数据库&大数据&数据科学 • 上一篇    下一篇

量子原型聚类

刘翔1,3, 祝静1, 仲国强1, 顾永建2, 崔丽媛1   

  1. 1 中国海洋大学计算机科学与技术学院 山东 青岛 266100
    2 中国海洋大学物理与光电工程学院 山东 青岛 266100
    3 中国海洋大学创新教育实践中心 山东 青岛 266100
  • 收稿日期:2022-06-13 修回日期:2022-11-23 出版日期:2023-08-15 发布日期:2023-08-02
  • 通讯作者: 仲国强(gqzhong@ouc.edu.cn)
  • 作者简介:(liuxiang@stu.ouc.edu.cn)
  • 基金资助:
    国家重点研发计划(2018AAA0100400);山东省自然科学基金(ZR2020MF131);山东省重大基础研究项目(ZR2021ZD19);青岛市科技计划项目(21-1-4-ny-19-nsh)

Quantum Prototype Clustering

LIU Xiang1,3, ZHU Jing1, ZHONG Guoqiang1, GU Yongjian2, CUI Liyuan1   

  1. 1 College of Computer Science and Technology,Ocean University of China,Qingdao,Shandong 266100,China
    2 College of Physics and Optoelectronic Engineering,Ocean University of China,Qingdao,Shandong 266100,China
    3 Innovation Center,Ocean University of China,Qingdao,Shandong 266100,China
  • Received:2022-06-13 Revised:2022-11-23 Online:2023-08-15 Published:2023-08-02
  • About author:LIU Xiang,born in 1998,master candidate,is a member of China Computer Federation.His main research interests include lightweight neural networks designing,underwater vision system and quantum machine learning.
    ZHONG Guoqiang,born in 1981,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include pattern recognition,machine learning and image processing.
  • Supported by:
    National Key Research and Development Program of China(2018AAA0100400), Natural Science Foundation of Shandong Province,China(ZR2020MF131),Major Basic R&D Projects in Shandong Province(ZR2021ZD19) and Science and Technology Program of Qingdao(21-1-4-ny-19-nsh).

摘要: 经典机器学习算法的量子化重构是量子机器学习领域的一个重要研究方向。聚类作为一类在机器学习领域被广泛应用的算法,其量子化重构也拥有较高的研究价值。目前的量子机器学习算法大多存在复现难度大、难以与经典算法形成直观对比等问题。为解决这些问题,提出了一种量子原型聚类算法(Quantum Prototype Clustering,QPC),该算法可以很方便地在现有的通用性量子计算设备上部署。该方法首先结合单量子位旋转特性,寻找信息损失最小的特征映射方式,使用双维度特征数据制造单量子位旋转;然后,基于多量子位纠缠及纠缠系统坍缩的特性,设计了一种用于制造特定量子纠缠系统和测量纠缠系统坍缩结果的量子线路。根据纠缠系统中受控量子位旋转角和纠缠系统坍缩结果的关系,并结合闵可夫斯基距离的定义,推导了一种用于评估输入样本相似性的量子距离。该量子距离测量模块与经典计算机中的距离计算模块具有相同的输入输出形式,可以不加修改地替换掉原型聚类中的闵可夫斯基距离计算,从而将经典的原型聚类算法重构为QPC。在来自kaggle和scikit-learn的多组公开数据集上进行的多次重复实验表明,在平均样本中心距等评价指标上,QPC与经典的原型聚类算法无明显差别。

关键词: 量子计算, 量子机器学习, 聚类算法, 原型聚类

Abstract: Quantitative reconstruction of classical machine learning algorithms is one of the significant research directions in the field of quantum machine learning.The quantitative implementation of clustering algorithm,which has been widely used in the machine learning area,is worth studying.Most of the current quantum machine learning algorithms suffer from the difficulty of reproduction and the difficulty of forming direct comparisons with classical algorithms.To address these problems,this paper proposes the quantum prototype clustering algorithm that can be easily deployed on existing general-purpose quantum computing devices.Combining the rotation property of single quantum bit(qubit),and finding the feature mapping method with minimal information loss,the single qubit rotation is created using two-dimensional feature data.Then,based on the properties of multi-qubit entanglement and the collapse of the entangled system,a quantum circuit is designed for generating a specific quantum entangled system and measuring the collapsed result of entangled system.Based on the relationship between the rotation angle of controlled qubits in the entangled system and the collapse result of the entangled system,and combined with the definition of Minkowski distance,a quantum distance for evaluating the similarity of input samples is then derived.Both the quantum distance calculation module and its counterpart in classic computer have the same forms of input and output,so that the latter can be replaced by the former without modification,hence the prototype clustering algorithm is quantitatively reconstructed into QPC.Several replicated experiments on multiple publicly available datasets from kaggle and scikit-learn show that the QPC performs similarly to classic prototype clustering algorithm in terms of many evaluation metrics,such as the mean sample-centroid distance.

Key words: Quantum computation, Quantum machine learning, Clustering algorithm, Prototype clustering

中图分类号: 

  • TP181
[1]CILIBERTO C,HERBSTER M,IALONGO A D.Quantum machine learning:a classical perspective[J].Proceedings of the Royal Society A:Mathematical,Physical and Engineering Sciences,2018,474(2209):20170551.
[2]BIAMONTE J,WITTEK P,PANCOTTI N,et al.Quantummachine learning[J]Nature,2017,549(7671):195-202.
[3]MISHRA N,KAPIL M,RAKESH H.Quantum Machine Lear-ning:A Review and Current Status[J].Data Management,Analytics and Innovation,2019,2:101-145.
[4]SHOR W P.Algorithms for quantum computation:Discrete lo-garithms and factoring[C]//Proceedings 35th Annual Sympo-sium on Foundations of Computer Science.1994:124-134.
[5]GROVER L K.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325.
[6]HUANG Y M,LEI H,LI X Y.Overview of Quantum machine learning algorithms[J].Journal of Computer Science,2015,41(1):145-163.
[7]HARROW A W,HASSIDIM A,LLOYD S.Quantum algorithm for linear systems of equations[J].Physical Review Letters,2009,103(15):150502.
[8]BHARTI K,HAUG T,VEDRAL V.Machine Learning meets Quantum Foundations:A Brief Survey[J].arXiv:2003.11224,2020.
[9]ZHOU Z H.Machine Learning[M].Beijing:Tsinghua University Press,2016:202-211.
[10]WIEBE N,BRAUN D,LLOYD S.Quantum algorithm for data fitting[J].Physical Review Letters,2012,109(5):050505.
[11]CHILDS A M,KOTHARI R,SOMMA R D.Quantum algo-rithm for systems of linear equations with exponentially improved dependence on precision[J].SIAM Journal on Computing,2017,46(6):1920-1950.
[12]SCHULD M,SINAYSKIY I,PETRUCCIONE F.An introduction to quantum machine learning[J].Contemporary Physics,2015,56(2):172-185.
[13]WITTEK P.Quantum machine learning:What quantum computing means to data mining[M].Academic Press,2014:132-133.
[14]CASPER E,HUNG C C,JUNG E,et al.A quantum-modeled k-means clustering algorithm for multi-band image segmentation[C]//Proceedings of the 2012 ACM Research in Applied Computation Symposium.Texas,USA,2012:156-163.
[15]ARUNACHALAM S,DE W R.Guest column:A survey ofquantum learning theory[J].ACM SIGACT News,2017,48(2):41-67.
[16]ADCOCK J,ALLEN E,DAY M,et al.Advances in quantum machine learning[J].arXiv:1512.02900,2015.
[17]KERENIDIS I,LANDMAN J,LUONGO A,et al.Q-means:a quantum algorithm for unsupervised machine learning[J].ar-Xiv:1812.03584,2019.
[18]XIAO J,YAN Y,ZHANG J.et al.Quantum-inspired geneticalgorithm for k-means clustering[J].Expert Systems with Applications,2010,37(7):4966-4973.
[19]ENNIOGI T.Quantum K-Means[EB/OL].https://github.com/enniogit/Quantum_K-means.
[20]ZHANG Y,NI Q.Recent advances in quantum machine learning[J].Quantum Engineering,2020,2(1):e34.
[21]O'QUINN W,MAO S.Quantum Machine Learning:Recent Advances and Outlook[J].IEEE Wireless Communications,2020,27(3):126-131.
[22]DUNJKO V,WITTEK P.A non-review of Quantum MachineLearning:trends and explorations[J].Quantum Views,2020,4:32-45.
[23]POMERANCE C.A tale of two sieves[J].Notices of the American Mathematical Society,1996,43(12):1473-1485.
[24]BENNETT C H,BERNSTEIN E,BRASSARD G,et al.Strengths and weaknesses of quantum computing[J].SIAM Journal on Computing,1997,26(5):1510-1523.
[25]BARZ S,KASSAL I,RINGBAUER M,et al.A two-qubit photonic quantum processor and its application to solving systems of linear equations[J].Scientific Reports,2014,4:6115-6120.
[26]CAI X D,WEEDBROOK C,SU Z E,et al.Experimental quantum computing to solve systems of linear equations[J].Physical Review Letters,2013,110(23):230501.
[27]ZHENG Y,SONG C,CHEN M C,et al.Solving systems of linear equations with a superconducting quantum processor[J].Physical Review Letters,2017,118(21):210504.
[28]LLOYD S,MOHSENI M,REBENTROST P.Quantum algo-rithms for supervised and unsupervised machine learning[J].arXiv:1307.0411,2013.
[29]REBENTROST P,MOHSENI M.LLOYD S.Quantum support vector machine for big data classification[J].Physical Review Letters,2014,113(13):130503.
[30]WOLD S,ESBENSEN K,GELADI P.Principal component ana-lysis[J].Chemometrics and Intelligent Laboratory Systems,1987,2(1/2/3):37-52.
[31]LLOYD S,MOHSENI M,REBENTROST P.Quantum principal component analysis[J].Nature Physics,2014,10(9):631-633.
[32]SENTÍS G,BAGAN E,CALSAMIGLIA J,et al.Quantumchange point[J].Physical Review Letters,2016,117(15):150502.
[33]ADACHI S H,HENDERSON M P.Application of quantum annealing to training of deep neural networks[J].arXiv:1510.06356,2015.
[34]SCHULD M,KILLORAN N.Quantum machine learning in feature Hilbert spaces[J].Physical Review Letters,2019,122(4):040504.
[35]CASPER E,HUNG C C.Quantum modeled clustering algo-rithms for image segmentation[J].Progress in Intelligent Computing and Applications,2013,2(1):1-21.
[36]ZHANG H,MAO S,WU W,et al.A Review of quantum computing complexity theory[J].Journal of Computer Science,2016,39(12):2403-2428.
[37]ZHONG H,HUI W,DENG Y,et al.Quantum computational advantage using photons[J].Science,2020,370:1460-1463.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!