计算机科学 ›› 2023, Vol. 50 ›› Issue (8): 27-36.doi: 10.11896/jsjkx.220600124
刘翔1,3, 祝静1, 仲国强1, 顾永建2, 崔丽媛1
LIU Xiang1,3, ZHU Jing1, ZHONG Guoqiang1, GU Yongjian2, CUI Liyuan1
摘要: 经典机器学习算法的量子化重构是量子机器学习领域的一个重要研究方向。聚类作为一类在机器学习领域被广泛应用的算法,其量子化重构也拥有较高的研究价值。目前的量子机器学习算法大多存在复现难度大、难以与经典算法形成直观对比等问题。为解决这些问题,提出了一种量子原型聚类算法(Quantum Prototype Clustering,QPC),该算法可以很方便地在现有的通用性量子计算设备上部署。该方法首先结合单量子位旋转特性,寻找信息损失最小的特征映射方式,使用双维度特征数据制造单量子位旋转;然后,基于多量子位纠缠及纠缠系统坍缩的特性,设计了一种用于制造特定量子纠缠系统和测量纠缠系统坍缩结果的量子线路。根据纠缠系统中受控量子位旋转角和纠缠系统坍缩结果的关系,并结合闵可夫斯基距离的定义,推导了一种用于评估输入样本相似性的量子距离。该量子距离测量模块与经典计算机中的距离计算模块具有相同的输入输出形式,可以不加修改地替换掉原型聚类中的闵可夫斯基距离计算,从而将经典的原型聚类算法重构为QPC。在来自kaggle和scikit-learn的多组公开数据集上进行的多次重复实验表明,在平均样本中心距等评价指标上,QPC与经典的原型聚类算法无明显差别。
中图分类号:
[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. |
|