欢迎访问一起赢论文辅导网
SCI期刊论文
当前位置:首页 > SCI期刊论文
量子机器学习算法综述
来源:一起赢论文网     日期:2018-09-05     浏览数:2420     【 字体:

 40卷 计算机学报 Vol.402017论文在线出版号No.62 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.62———————————————本课题得到国家自然科学基金(61502082)、中央高校基本科研业务费基础研究项目(ZYGX2014J065)资助. 黄一鸣(通讯作者),男,1991年生,博士生,主要研究领域为数据分析,数据挖掘和量子机器学习,E-mail:yiminghwang@gmail.com. 雷航,男,1960年生,博士,教授,CCF会员(16350M, 主要研究领域为大数据挖掘和嵌入式系统.E-mail:hlei@uestc.edu.cn. 李晓瑜(通讯作者),女,1984年生,博士,副教授,CCF会员(12052M,主要研究领域为数据分析,量子计算和量子机器学习.E-mail:xiaoyu33521@163.com.量子机器学习算法综述黄一鸣1)雷航1)李晓瑜1)1)(电子科技大学信息与软件工程学院, 成都市610054)摘要 机器学习在过去十几年里不断发展,并对其他领域产生了深远的影响。近几年,研究人员发现结合量子计算特性的新型机器学习算法可实现对传统算法的加速,该类成果引起了广泛的关注和研究。因此,本文对近十年的量子机器学习算法进行总结、梳理。首先,介绍了量子计算和机器学习的基本概念;其次,从四个方面分别介绍了量子机器学习,分别是量子无监督聚类算法、量子有监督分类算法、量子降维算法、量子深度学习;同时,对比分析量子机器学习算法与传统机器学习算法的区别和联系;最后,总结该领域存在的问题及挑战,并对量子机器学习未来工作进行展望。关键词 量子机器学习;量子计算;大数据;人工智能;量子深度学习中图法分类号TP181论文引用格式:黄一鸣,雷航,李晓瑜, 量子机器学习算法综述,2017,Vol.40,在线出版号No.62HuangYi-mingLeiHangLiXiao-Yu,ASurveyonQuantumMachineLearning,2017,Vol.40,OnlinePublishingNo.62ASurveyonQuantumMachineLearningHuangYi-ming1)LEIHang1)LIXiao-Yu1)1)(Schoolofinformationandsoftwareengineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu,610054)Abstract Withtremendousdevelopment of classical machinelearninginpast decades, it hasinfluencedonmanydifferentfieldsasanessentialpartofdatascience.Recentyears,asaninnovativetypeofmachinelearningalgorithms, quantummachine learning plays high parallel performance based on quantummechanics.Consequently, itspeedsupsomeofconventionalalgorithms.Researchersinquantummachinelearningfocusonimprovingperformanceofclassicalmachinelearningthroughquantumcomputationandexploringthepossibilityof combination of machine learningwith quantummechanics, andpresentingsome newalgorithms. Theframeworkof quantummachinelearningmainlycontainsthreesteps: 1) Loadandinput classical data. It isconvertingclassical informationintoquantuminformation. Makingfull useof highperformanceof quantumcomputation, it isnecessarytoencodeclassical datatoquantumdataaccordingtoquantumrepresentation. 2)Construct seriesof unitaryoperatorsandusethemtoprocessquantumdata. Thebasicprincipleof quantumcomputationisthatalltheoperationsmust followtheunitarycharacteristics.Thereby, itisnotpossibletoreviseall classical algorithmstoquantumenvironment, andnot all thequantumalgorithmscanprovideexponentialspeed-up. 3)Readandoutput thelearningresult.Afterthefirst twosteps, thequantummachinelearningresultsarequantumstates. Inordertoreadandoutputtheusefullearningresult, itneedssomenecessarymeasurementstoextract relevant information. Therearethreekinds of researchinthis field: 1) Usequantumcomputingacceleratesthecostlypart oftraditional algorithm. Thisworkisthehybridofclassical algorithmandquantum网络出版时间:2017-05-19 12:49:46网络出版地址:http://kns.cnki.net/kcms/detail/11.1826.TP.20170519.1249.008.html2 计算机学报 2017parts. Thereisnochangeof themainideaof learningalgorithm. But complexpartsarerunningonquantumdevices, anditmakesfulluseofquantumcomputingtospeedupcounterparts. 2)Borrowthephysicsconcepttoproposenewalgorithms. It isbasedonthemathematical frameworkof quantummechanics. Andresearchersdevelopmoreefficientmethodstosolveoptimizationproblem. 3)Usemachinelearningmethodstosolvesomephysicsissue, suchasquantumtomographybyusingcompresssensing. Withthepowerofmachinelearning,researcherscanexplorequantumworldfromanotherperspective, viceversa. Quantummachinelearningsolvesclassical data mininganddata analysis problems fromanother perspective. There are some difficulties inbuildinggeneral quantumcomputer, researchersstill makesolidprogress. Withthedevelopment of quantumtechniques, practical quantummachine learningalgorithms will increasinglybe presented. Therefore, sometypical algorithmsofquantummachinelearningaresurveyedinthispaper. First, it introducesthefundamentalconceptsofquantumcomputationandclassicalmachinelearning, includingquantumstates, quantumgate, andmeasurement. Secondly, it summarizesthequantummachinelearningalgorithmsfromfour aspectsincludingquantumunsupervisedclusteringalgorithm, quantumsupervisedclassificationalgorithm, quantumdimensionreductionalgorithm, quantumdeeplearning. It collectssometypical algorithmsfor everypart. Meanwhile, itanalyzesandmakesacomparisonofcomputationalcomplexitybetweenclassicalmachinelearningandquantummachinelearning.Finally,itreconfirmstheproblems,challengesandfutureresearchworksforquantummachinelearningalongwithaninsightofquantumcomputationforbigdata.Keywords quantummachinelearning; quantumcomputation; bigdata; artificial intelligence; quantumdeeplearning1引言近十几年时间里,机器学习快速崛起,已经成为大数据时代下的技术基石。机器学习根据已有数据进行学习策略的探索和潜在结构的发现,依据所得模型进行预测及分析[1]。机器学习源于人工智能和统计学,其应用极其广泛。从数据挖掘到人脸识别,从自然语言处理到生物特征识别,从垃圾邮件分类到医学诊断,社会生活的各个方面都被机器学习技术所影响。随着信息技术不断发展,信息化将各行业紧密联系起来,产业数据成爆炸式增长。这种增长不仅是数据量的增长,还包括数据种类、结构和产生速度上的增长。最近几年全球数据量的增长率接近24%[2]。以Google为首,凭借数据服务为核心、机器学习技术为支撑的一大批IT公司占领数据挖掘与信息化的市场。他们掌握海量数据,使用机器学习技术挖掘潜在价值信息,提供数据服务,改变社会生活各个方面。数据的增长不仅带来丰厚的利润,同时也带来技术的挑战。不少传统机器学习算法已无法应对大数据时代海量数据的处理和分析,所以不得不寻找新的方法来解决问题。最近不少研究机构及大型IT公司都将目光集中到了量子计算上,想通过量子计算的独特性质,解决传统算法的运算效率问题。传统电子计算机存储电平的高低,每次只能处理一个比特的状态数据。量子计算机存储量子比特,一个量子比特可表示量子态01的叠加,一次运算就可同时处理两个状态的信息。以此类推,经典计算机对2n比特的数据执行相同计算需要2n次操作,而量子计算机只需要对n个量子比特进行一次操作即可。正因如此,量子计算不管在数据存储能力还是数据处理能力上都理论上远超经典计算。早在1982年,Feynman指出基于量子力学建造的计算机对特定问题的求解是传统计算机无法比拟的[3]1994年,Shor提出了一种里程碑式的量子因子分解算法[4],称为Shor算法。计算步骤上,传统大数因子分解的最佳算法的时间复杂度随问题规模成指数倍增加,而Shor算法可在多项式时间内完成。1997年,Grover提出一种量子搜索算法[5],该算法相比传统无序数据库搜索算法有着平方级效率的提升。现有的量子算法1,大多相较于对应的经典算法有着明显提速效果。由此,研究学者猜想既然量子计算对特定经典问题的求解有显著提速,是否可将其应用到机器学习领域,解决目前处1http://math.nist.gov/quantum/zoo/论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 3理大数据时计算效率低的问题。近年来出现越来越多结合量子计算和机器学习的研究[6][7][8]。研究人员一方面希望通过量子计算解决机器学习的运算效率问题;另一方面探索使用量子力学的性质,开发更加智能的机器学习算法。虽然量子计算机的研究不断深入,但依然有不少问题有待解决[9],例如如何保持量子的相干性、如何降低苛刻的环境条件等。同时,量子计算机的建造以及量子算法的提出都涉及诸多领域要素,量子机器学习理论现在依旧处于一个起步阶段,至今没有形成如经典机器学习领域完备的理论体系,大多研究还处于探索实验阶段。量子机器学习领域的研究最早可追溯到1995年对量子神经网络的研究:Kak最先提出量子神经计算的概念[10]。随后研究人员提出了各类量子神经网络模型,如Behrman提出的基于量子点神经网络模型[11]Toth提出了量子细胞神经网络[12]Ventura提出的使用量子叠加态表示网络[13]Matsui提出了通过量子门电路实现的神经网络[14],周日贵提出了量子感知机[15]Schuld提出了由量子随机行走构建神经网络[16],等等。这些不同种类的量子神经网络模型的构建,均是基于量子力学特性与不同数据结构的结合。该领域研究的一个难点在于如何将神经网络的非线性映射结构同量子计算的线性变换结合在一起,即如何实现神经网络的量子演化。研究人员发现量子特性有助于研究无监督聚类问题,故提出了量子无监督聚类算法。2001年,Horn最早将量子力学特性引入传统聚类算法,其将薛定谔方程与Parzen窗估算量的极大值求解联系起来,用于发现数据的聚类中心[17]2013年,Lloyd等人将量子态的叠加性应用到经典向量表示上,提出量子K-means算法,该算法理论上能够实现海量数据的高效聚类[18]。同年,Aïmeur等人提出了量子分裂聚类算法,其借助Grover变体算法进行子过程中最大距离的快速搜索[19][20]。类似还有研究人员结合监督分类算法和量子计算,提出量子有监督分类算法,例如2014年,微软的Wiebe等人提出了用量子态的概率幅表示经典向量,并通过比较两个量子态间距离完成量子最近邻算法[21]。同年,Rebentrost等人首次提出使用量子系统的密度矩阵进行支持向量机中核矩阵的表示[22]2016年,微软的Nathan等人提出了量子深度学习的概念,首次将量子计算同深度学习相结合,其通过量子采样实现受限玻尔兹曼机的梯度估计,旨在加速深度网络的训练[23]。上述量子机器学习算法的核心大多还是与传统算法相同,主要区别在于通过量子计算的高并行性去处理计算耗时的子步骤。其他关于量子计算及机器学习核心问题的研究也进一步推动量子机器学习的发展。首先,Giovannetti等人于2008年提出了量子随机存取存储器(quantumrandomaccess memory, QRAM)[24][25],随后许多量子机器学习算法相继产生,如2014Lloyd基于QRAM提出量子主成分分析(quantumprinciplecomponent analysis, QPCA)算法等[26]。其次,Harrow等人于2009年,提出用量子算法解决线性系统的方程问题[27],常被研究人员成为HHL算法;2015年,Childs也对该问题进行了相关研究[28],进一步拓展了量子算法对线性系统问题的解决能力。很多传统机器学习问题最终与最优化问题的求解相关,而最优化问题常涉及线性方程组的求解,所以通过该技术可有助经典机器学习中最优化步骤的提速。例如,Rebentrost2014年提出的量子支持向量机就用到了量子线性方程求解算法[22]。很多算法是以QRAM物理实现为前提,利用QRAM实现任意量子态的制备,继而进行后续量子态计算。但实际上QRAM只是个理论模型,至今仍没有任何实验性的研究对其进行验证。对于量子机器学习的可学习性及其与经典算法的比较,也是研究人员的关注点之一。2004Servedio对传统机器学习算法的可学习性与量子算法的可学习性进行了分析与比较[29]。随后,2006年,Aïmeur等人提出了在量子环境下完成机器学习任务的猜想[30]Yoo等人从二分类问题上对量子机器学习与传统机器学习进行了比较,指出量子的叠加性原理使得量子机器学习算法运算效率明显优于传统算法,并从学习的接受域上进行了比较,发现量子机器学习的接受域较大,从而决定了学习效率优于传统算法[31]。随着大数据时代的到来,传统算法对于海量数据的处理能力,也日益捉襟见肘。这就进一步促使研究人员考虑量子机器学习对大数据问题的解决能力和可行性。首先,2015年初陆朝阳教授研究小组的相关研究开始关注量子机器学习与大数据的结合[40]。随后,年底王书浩和龙桂鲁教授对量子机器学习及大数据领域的应用做了综述性介绍[32]。这些都进一步推动了量子计算在数据挖掘和数据分析方面的研究和应用。以D-WaveGoogle为首的公司对该领域也进行了研究。2008年,GoogleNevenD-Wave4 计算机学报 2017年公司的Rose等人在其研发的超导绝热量子处理器上使用量子绝热算法解决图像识别问题[33][34],此后他们又做了一系列将量子绝热算法应用到人工智能领域的研究[35]~[38]。这一系列量子绝热算法没有通过量子门电路进行量子计算,而是运行在D-Wave研发的特定量子芯片上,并且其运行的环境条件也相对苛刻。目前他们研究的算法还有很多限制,其商业领域的实际应用还有一段距离,不过已经向量子机器学习的产业化应用迈出了坚实的一步。在量子机器学习的物理实验验证方面,全球的研究人员也在努力不懈。2015年,潘建伟教授团队首次在小型光量子计算机上实现并验证了Lloyd提出的K-means算法[39]ZhaokaiLi等人也于同年实验验证了量子支持向量机算法,并进行了手写数字的二分类实验验证[40]。虽然实验的数据规模受限于当前量子计算机的量子比特数,但足以证明量子机器学习算法的可行性,且鼓舞我们在该领域进行更加深入的研究,以获得解决海量数据分析处理的有用工具。相信随着制造工艺的不断提升,量子计算及量子机器学习理论的不断完善,更多巧妙结合物理原理和机器学习理论的新型算法将被提出。量子机器学习将极大促进现有机器学习的发展,产生出更加高效、强大的学习算法。2量子计算与机器学习2.1量子计算所有信息计算的本质都是一个物理过程[41]。计算设备的物理特性决定其计算能力。根据Moore定律[42],集成电路上可容纳的晶体管数目约每隔24个月增加一倍。按此速度发展,一方面芯片元件集成度的提高会导致单位体积内散热增加,由于材料散热速度有限,就会出现计算速度的上限,产生“热耗效应”;另一方面元件尺寸的不断缩小,在纳米甚至埃尺度下经典世界的物理规则不再适用,出现“尺寸效应”[43]。综上,随着集成技术的提升,为解决“热耗效应”和“尺寸效应”不得不重新考虑能适用于微观世界的新型计算机模型。由此量子计算应运而生。它最早的想法源于Benioff提出的基于量子力学原理的可逆计算模型[44],后来Feynman进行了扩展。2.1.1量子态不同于经典电子计算机,量子计算机操作的基本数据单元是量子比特(qubit)。物理上,量子比特可以有不同方法的实现,可由两能级原子系统来表示,也可由光的不同偏振方向来表示。一个量子态通常用狄拉克符号·来表示。数学上,它为一个n维希尔伯特空间中的复向量,如式(1)所示。1=niii j a=å (1)(1)i 为基态,ia为复数,是每个态的概率幅。按照量子力学原理,如果测量该量子态j,最后会以2ia 的概率波包塌缩到基态i 上,因此每个基态的概率幅ia必须满足式(2)211niia== å (2)多个量子比特组成的集合常称为量子寄存器,除了使用狄拉克符号也可以使用向量的形式表示。例如可使用n维向量表示一个n位量子寄存器2 10=niii j a-= å ,如式(3)所示。012 1naaja-æ öç ÷ç ÷=ç ÷ç ÷ç ÷è øM(3)其中每个基态i 都可以展成二进制形式,如2 1 111,...,1nn- =14243。111,...,11对应一位量子比特。2.1.2量子门与经典计算机相同,量子计算机对量子比特的任何操作都可通过量子门实现。不同于经典计算机进行门电路操作后产生的能量耗散。例如01的与运算这是个不可逆且能量耗散的过程,量子计算机可通过幺正变换实现可逆计算,从而解决能耗上的问题。所以全部量子门都对应一个幺正算子。任何n位量子比特门都可用n×n的矩阵U来表示,如式(4)。论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 5( )11122, 121 22nnn n niji ju uU uu u=é ùê ú= =ê úê úë ûLM O ML(4)因为U实质为一个幺正变换,则必须满足(5)条件。† †UU UU I = = (5)其中†UU的共轭转置。对量子态2 10=niii j a-= å进行U变换,可得式(6)2 1 2 10 00 011121 121 222 1 2 1=n nnn n nn nij j ij iU u j iu uu uj a ba ba ba b- -= =- -=é ù æ öé ùç ÷ ê úê úç ÷ ê ú= =ê úç ÷ ê úê úç ÷ ê úë û ç ÷ê úë û è øå åLM O MM ML(6)2.1.3测量量子计算的结果依旧处于一个叠加态,为了得到该结果,必须对该量子态进行测量,使叠加态波包塌缩到一个基态。定义一组测量算子{ }mM ,该组测量算子还需满足完备性。†m mMM I = å (7)m对应测量的可能结果,若使用该测量算子对量子态j进行测量,最终得到m的概率为:( )†m mpm MM j j = (8)测量后的量子态为:†mm mMMMjj j(9)2.2机器学习与深度学习机器学习属于人工智能领域,主要利用计算机分析处理已知数据,从数据中自动“学习”潜在规则,并将此规则用于对未知数据的预测。例如对手写字符的识别,需要将字符图像信息转换成特征数据集X,( ) ( ) ( ) ( )( )1 2 2, ,..., ,...,mX=x x x x 。数据集总共有m 个样本,( ) ix 为第i 个样本。( ) ( ) ( ) ( ) ( )( ) 1 2, ,..., ,...,i i i i ij nx x x x = x ,每个样本有n个特征,( ) ijx 为第j个特征。然后机器使用学习算法对手写字符集X进行潜在规则的提取,最后使用该规则进行字符的判断。传统机器学习主要分为监督学习、无监督学习、半监督学习及增强学习。监督学习的训练样本都有人为标注分类结果的标签。输入训练样本,通过最小化代价函数,找出样本特征与标签之间的映射关系(学习模型)。新的未标注数据通过训练得到的学习模型进行分类。无监督学习,没有标注标签的训练集,学习算法自行寻找数据集当中的潜在规则,该类以聚类算法最为常见。半监督学习是介于监督与无监督之间的一种学习算法,为解决大数据量及监督学习标记代价高的问题,其主要使用较少的带标签及较多的未带标签数据进行训练分类。增强学习源于心理学的奖励与惩罚,通过刺激进而逐步优化,通过不断的反馈达到最优。机器学习相较于以往基于人工规则的学习方法,显示出强大处理分析能力。各类学习算法不断被提出,例如通用的逻辑回归(logisticregression,LR[45]、支持向量机[46]supportvectormachine,SVM)、关联规则挖掘[47]AssociatedRulesMiningARM)算法等;随着研究的逐步深入,研究人员发现以上学习算法具有一定的局限性。相对于深度学习,上述算法的输入特征需要使用专业领域知识进行筛选提取,同时该学习算法均使用单层非线性变换进行数据分析处理。这种单层非线性变换结构,制约了其对现实中更加复杂高维的函数的表示能力。为了达到更好描述复杂世界,解决实际问题的目的,学习算法需要拥有大量的训练数据作为基础,使用专业的领域知识来提取优质的特征,通过强大的计算能力求解问题。通常训练样本无法保证充足,同时特征的提取也直接影响了学习算法的表现能力。因此,深度学习应运而生。深度学习的概念最早由Hinton2006年提出,文章指出多层的神经网络能更好地表达数据本质,并且可以通过逐层初始化的方法解决多层复杂网络训练困难的问题[48]。之后,不管是学术还是工业界,深度学习都引起了广泛的关注。大量的实验证明深度学习相对于浅层学习,精度上有明显的提高。不管从语音识别还是图像识别领域,深度学习都能更好地刻画和承载海量数据中更丰富的信息。典型的深度学习结构分为以下三种[49]1)生成型,如深度信念网络[50]。该类模型能表达输出与输入样本数据间的联合概率分布,解决网络初始权重设置问题,提升模型性能及收敛速度[51]2)区分型,如卷积神经网络[52]。该类模型使用权值共享,同一层神经元共享一个权值集合,所以网络中的自由参6 计算机学报 2017年数少于传统网络[53]3)混合型,该模型通过受限玻尔兹曼机预训练产生,再使用反向传播算法(BackpropagationalgorithmBP)优化深度信念网络的权值,这样就比单用BP算法对卷积神经网络进行训练更优。3量子机器学习量子机器学习借助量子计算的高并行性,实现进一步优化传统机器学习的目的。AaronsonServedio以及Cheng等人对量子态的可学习性进行了研究[29],[54],[55]Servedio从信息论的角度指出量子信息和经典信息的可学习性是等价的,这也促使了量子机器学习研究的发展[56]~[58]ChengServedio的基础上提出量子学习算法主要分为两大类研究,一类是量子计算学习(quantumcomputationallearning, QCL),另一类是量子概率学习(quantumstatisticallearning,QSL)[29]QCL主要研究两点。1)如何利用量子力学原理改进传统机器学习过程,提高计算效率,降低计算复杂度[18],[23],[58]~[65]2)利用统计学习理论去解决量子状态层析(quantumstatetomography,QST)、寻找量子系统的隐藏结构等问题[66]~[69]。至今绝大部分前人工作都集中于解决第一种计算复杂性问题,故本文主要介绍该类量子机器学习算法。并非所有经典学习算法的步骤都可通过量子特性进行加速。量子力学公设指出封闭量子系统通过酉变换来刻画量子态的演化[70],即量子态演化需要由酉算子来实现。近年来,龙桂鲁教授研究小组提出使用酉变换的线性组合,也可实现量子计算[71]。量子机器学习算法的基本原理是需将经典学习算法中的信息映射成量子态,然后对量子态进行酉演化操作,进而达到计算的目的。所以因此,只有满足以上计算条件的经典学习步骤才能实现加速。为使用量子特性达到加速的目的,就必须对传统算法进行相应的改写,使其满足上述量子计算的基本要求。当前的研究大多集中于用量子算法替代原有经典算法的特定子过程,进而达到降低计算复杂度,提高算法效率的目的。量子机器学习算法一般需要经过以下步骤:步骤1:将经典信息转换成量子信息。为了发挥量子计算机的高并行特性,必须对经典信息进行编码,将其转换成量子信息,这就好比将一门语言翻译为另外一门语言。合适、巧妙的编码将更加有效的利用量子计算的潜力。步骤2:传统机器学习算法的量子版转换。由于量子计算机和经典电子计算机的操作单元不同,无法将所有的经典计算机的方法都移植到量子计算机上,并且不是所有在量子计算机上的操作都会有指数性的加速。所以设计出适用于量子计算机的算法将十分重要。量子机器学习算法的设计,既要结合经典算法的数据结构、数据库等技术,同时,还要不断设计出更多适合量子理论的算法模型。这个建模的过程,也是步骤2的重点和难点。步骤3:提取最终计算结果。由于计算结果为量子态无法直接使用,需要经过量子测量操作,使量子叠加态波包塌缩至经典态,将经典信息提取出来。已有的量子机器学习主要可以分为以下三类,分别是:(1). 第一类量子机器学习。该类算法将机器学习中复杂度较高的部分替换为量子版本进行计算,从而提高其整体运算效率,如图1所示。该类量子机器学习算法整体框架沿用原有机器学习的框架。其主体思想不变,不同点在于将复杂计算转换成量子版本运行在量子计算机上,从而得到提速。该类研究的代表性成果有:Lloyd教授提出的QPCAQSVM(quantumsupportvectormachine,QSVM)[18],[22]等。图1第一类量子机器学习(2). 第二类量子机器学习:该类算法的特点是寻找量子系统的力学效应、动力学特性与传统机器学习处理步骤的相似点,将物理过程应用于传统机器学习问题的求解,产生出新的机器学习算法,如图2所示。该类算法与第一类不同,其全部过程均可在经典计算机上进行实现。在其他领域也有不少类似思路的研究,如退火算法、蚁群算法等。该类量子机器学习算法的代表性研究有Horn的基于量子力学的聚类算法[17]。论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 72第二类量子机器学习(3). 第三类量子机器学习:该类算法主要借助传统机器学习强大的数据分析能力,帮助物理学家更好的研究量子系统,更加有效的分析量子效应,作为物理学家对量子世界研究的有效辅助,如图3所示。该类算法的提出将促进我们对微观世界进一步的了解,并解释量子世界的奇特现象。该类算法的代表性研究有:Gross的基于压缩感知的量子断层分析[68][69]等。图3第三类量子机器学习由于量子机器学习的大多数研究集中于第一类算法,第二类算法的研究还较少,第三类量子机器学习算法主要应用于物理领域。所以,本部分后续小节将着重介绍第一类量子机器学习算法。本文分别从无监督量子聚类算法、有监督量子分类算法、量子降维算法、量子深度学习等几个方面进行,最后会对时下主流的量子机器学习算法进行比较和分析。3.1无监督量子聚类算法3.1.1量子K-means算法聚类算法是无监督学习算法中较为重要的一类。以最普遍使用的k-means算法为例,该算法以距离的远近作为样本相似性指标,即两个样本的距离越近相似程度就越高[72]。当遇到海量样本数据时,k-means算法存在时间开销较大的缺点。Lloyd等人于2013年提出了量子版最近中心算法[18]。量子最近中心算法可视为经典k-means聚类算法的子过程,使用该方法可对经典算法进行指数级提速[18]。该算法的加速来源于量子计算机具有高维空间中对向量和张量操作的优势,这是由量子力学自身特性所决定的。量子力学使用希尔伯特空间中的向量来描述物理系统,而希尔伯特空间本身就是完备的线性空间,对量子态的操作即在线性空间中对向量的操作。同时,希尔伯特空间中的量子态满足叠加性原理,对多个态可实行并行操作,故计算效率远超经典计算。量子计算满足以上量子力学规律及数学特性,故量子机器学习能有效处理高维数据。量子最近中心算法的核心思想是对实向量间的距离作比较,通过寻找向量u与集合{} v 中的哪个量的距离最近,从而不断分类,进而不断自动获得聚类结果,即11argmin-=- ×åmcjjcm u v Lloyd通过式(10)将实向量 ( )0 1, ,..., =nu u u u 转换成量子态u,从而将向量的距离比较转换成量子态间的距离比较。= uuu(10)同时定义纠缠态j:11 102mcjju v jmj=æ ö= +ç ÷è øå (11)以及态f :11 102mcjjjmf=æ ö= -ç ÷è øå u v (12)其中u为实向量u的范数,cjv c簇的第j个向量,m为样本总数,( )2211-== + åncjjZ n u v 为归一化系数。这两个量子态的距离可通过式(13)得到。22 |iD Z fj = (13)2| fj 通过controlled-SWAP电路实现[73],如图4所示。8 计算机学报 2017年图4controlled-SWAP量子电路实现图4H代表Hadamard门,电路使能与否由第一个量子比特控制,即电路最上面的量子线对应的是控制比特,下面的两个量子线对应的是受控量子比特。controlled-SWAP电路[73]作用于输入量子态j和f 后,得到式(14)。( ) ( )1 10 12 2j j j j f f f f + + - (14)对第一位量子比特进行测量,得0的概率为( )2 1 10 = |2 2P fj + ,那么 ( )2| =2 0 1 P fj - 。k-means算法中初始点的选择十分重要,好的初始点将极大地缩短迭代次数。初始点选择的是否足够好,评判的一个标准是,需要尽可能将初始点稀疏分布于整个样本空间中,即各点之间距离尽可能大。为了优化初始点,Lloyd使用量子绝热演化算法来实现k-means++算法最优初始点的选择[74]。其基本思想为,首先初始化Hamiltonian量,如式(15)所示。0H I y y = - (15)令y j j = Ä Ä L1442443kk为初始点个数,( )11/mjm j j== å 。j为样本标签编码后的归一化量子态,m为样本总数。然后定义末态Hamiltonian如式(16)所示。末态Hamiltonian的基态即是满足稀疏分布的初始点,最后进行测量操作,提取基态信息即可。''121 1, 1kkji jis k kj ji iH v v j j j j=Ä Ä = - - ååLLv v(16)在量子机器学习算法的物理实验方面,我国的研究团队处于世界领先水平。2015年,潘建伟院士团队以小型光量子计算机为实验平台,首次对Lloyd教授于2013年提出的量子K-means算法进行了物理实验验证[39]。该实验将单光子作为一位量子比特,使用自发参量下转换技术制备纠缠的光子对,并使用干涉仪将参考向量即测试向量编码到量子态上。实验分别对468量子比特规模的算法进行了验证,结果指出传统机器学习中普遍存在的高维向量间距离和内积的计算可在量子计算机上实现,这表明量子计算机上实现的该部分运算其效率将优于传统算法,也预示着量子机器学习算法具有拥面向大数据分析处理的优势。3.1.2量子分裂聚类分裂分层聚类为聚类算法中简单常用的一类算法。该类算法,首先将所有数据点视为一个类,然后不断分裂类簇,直至每个类簇不能再分裂[75]。其算法流程,通常初始选取所有数据点中尽可能远的两个数据点,作为初始分裂的两个子类的代表,如式(17)所示;其次,计算其余所有点与这两个点的距离,根据离这两个点的远近进行分配;以此类推,直到每个类内部点的两两距离都小于某阈值,结束分裂。( ) max,, maxx yx yC CD C CÎ Î= -x yx y (17)maxD 表示类别xCyC之间的最大距离。若有n个样本,每个样本维度为m,则传统算法计算该步骤的时间复杂度为( )2On 。显然,若处理大量样本,且维数较高的数据集时,经典算法的计算效率就会较低。2007年,Aïmeur等人提出了通过结合量子计算,实现快速寻找最大距离点这个子步骤[19]。该方法的核心步骤是使用Durr1999年提出的Grover变体算法[76],通过该算法提高寻找数据集中距离最远的两点的计算效率。以下为该算法的核心流程思想:Quantumdivisiveclustering(D)输入:数据集D输出:聚类后数据集'D1. If(D内数据点均满足距离相似性条件)2. ReturnD3. Else{4. 初始化max0 d =5. Do6. Grover变体算法寻找最远距离点a,b7. If ( )max, d ab d >8. ( )max, d d ab =9. While(存在( )max, d ab d ³ )论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 910. Foreach D Î x11. x分配到对应的类簇a或类簇b12. Endfor13. D分裂形成类簇DaDb14. Quantumdivisiveclustering(Da)15. Quantumdivisiveclustering(Db)16. Endif该量子分裂聚类算法主要依靠Grover变体算法来解决数据集的最值问题,相比于对应的传统算法,其提速效果主要源于此部分。该算法对传统分裂聚类算法的主体框架并未进行改变,Aïmeur只是将传统分裂聚类算法中计算复杂性较高的部分单独提取出来,通过量子搜索算法进行提速。这种各取所长的有机结合思路,也为后面众多的量子机器学习算法提供了很好的借鉴意义。3.2有监督量子分类算法3.2.1量子最近邻算法最近邻算法为传统机器学习算法中关于分类的一种简单且有效的算法。该类算法核心思想是,对一个样本x,在特征空间中找出与该样本最邻近的k个点,然后根据这k个点的类别,使用分类决策规则(例如多数表决),决定x所属类别。相较于传统最近邻分类算法,Wiebe等人采用与Lloyd相似的研究思路,提出了量子最近邻算法[21]。首先他将经典信息中的非零数据编码到量子态的概率幅值上,通过controlled-SWAP电路计算相应两量子态的内积来确定量子态之间的距离。Wiebe通过式(18)(19)对向量u和向量v进行编码,其中向量中非零特征使用负指数形式表示,f f= =ji jii iji ji ji jiv v e u u e v为已知分类结果的向量,d为非零特征数。2 22 20 max max11 0 1 1jijiji ji iuu uu i er r df -¹æ öç ÷= - +ç ÷ç ÷è øå (18)2 22 20 max max11 1 0 1jijiji jiivv vv i er r df -¹æ öç ÷= - +ç ÷ç ÷è øå(19)maxr 为特征值上界,对u v 进行controlled-SWAP操作后即可得式(20)。( ) ( )2max22| 2 0 1 = - r uv P d (20)Wiebe等人也尝试使用两量子态的欧式距离来判定其分类规则(详见文献[21]),但实验结果显示该方法相比于内积方法,迭代次数更多,精度也低于内积方法。故而,量子欧式距离分类算法并未得到推广。3.2.2量子支持向量机支持向量机(supportvectormachine,SVM),在传统机器学习算法中,是一种重要的监督类线性分类算法,其思想是通过寻找最大间隔分类超平面进行分类[77],寻找最大间隔超平面问题可等价于式(21)。( ) ( ),1argmax minTi iibt b fì üï ïé ù +í ýë ûï ïî þww xw(21)上式中w是超平面的法向量,b是偏置,ix为第i个训练样本, {1,1} Î-it 为该训练样本的标签,( ) ( )1f-+Ti it b w w x 为样本点到超平面的距离。若分类正确,则 ( ) ( )Ti it b f + w x 0 ,否则( ) ( ) 0Ti it b f + w x <。其中,最接近分类超平面的样本点ix,这些点也称为支持向量。针对于这些支持向量,需要寻找一个超平面,使得这些支持向量到该超平面的距离最大。通过超平面的尺度变换可将问题转化为式(22)。( ) ( )2,1      argmin2s.t.    1bTn it b f + ³www x(22)寻找距超平面距离最大的支持向量,即一个优化求解问题,故而可通过Langrangian方法解决。通常引入核方法,将线性不可分的低维特征( )', xx变换成线性可分的高维特征( )', k xx ,再对高位特征进行分类[77],特征空间映射示意如图5所示。关于量子支持向量机算法的有关研究,最早是Anguita等人于2003年使用量子计算的方法,解决了SVM的训练效率问题[78]。随后,Rebentrost等人在2014年提出量子版本的SVM,其核心思想是利用量子算法解决训练数据的内积运算问题(核方法)[22]Rebentrost首先将特征向量的各维特征编码至量子态概率幅 ( )11=Ni i ij jx j-=×å x x ,其中N为特征维度,( )ijx 为第i个特征向量的第j个特征,10 计算机学报 2017ix 为特征向量范数。其次,制备如下量子态,如式(23)所示。( )11=cc-=×åMi iiN x i x (23)其中21c==åMiiN x ix为第i个训练样本。Rebentrost之后将核矩阵和量子系统的密度矩阵联系起来。由于核矩阵的每个元素为向量间的内积= ×ij i jK x x,且 ( ) ( )11|--= ×j i i i j jx x x x x x ,此时通过求密度矩阵c c的偏迹即可得到归一化核矩阵。( )( )2, 11tr |trMi j i ji jKxx i jN Kcc c== = åx x (24)其中, = | ×i j i j j ix x x x x x 。通过该方法,就使量子系统同传统机器学习的核矩阵联系起来,由于量子态之间的演化运算具有高并行性,通过该方法即可完成传统机器学习中对应核矩阵计算的加速。图5SVM特征空间映射示意图1Rebentrost等人也提出了量子版本最小二乘法支持向量机(least-squares support vector machine,LS-SVM)。他们将传统SVM分类问题转化为求解式(25)的问题。µb,s.t.  1FFd y(25)其中b为偏置,向量d的每个元素为支持向量距最优超平面的距离,b,d即表示分类超平面,且( ) ( )1b, 0,T TF-= d y ,( )1 2= , ,...,My y y y 为训练样本的1http://www.statsoft.com/Textbook/Support-Vector-Machines标签。10=TFK g-æ öç ÷+è ø11 1K核矩阵,g为可接受误差权重。最后,分类任务即转化为使用controlled-SWAP操作来比较b,d和输入样本x的距离,从而得到x所属类别。量子支持向量机算法的物理实验也有一些进展。最近ZhaokaiLi等人通过核磁共振的方法,在物理上实现了4量子比特的量子SVM[40],并对最基本的手写数字69进行识别,实验结果显示识别精度高达99%。虽然实验样本较小,但该实验显示出量子理论与机器学习算法结合的可行性。3.2.3量子决策树算法决策树模型是一种描述对象属性或特征,并与对象所属类别之间进行关系映射,所形成的树形结构模型[79]。树中每个节点代表一个对象,分为内部节点和叶节点(即最后一层节点)两种。内部节点代表对象的属性值,叶节点代表对象的类别。决策树分类过程,如图6所示。分类,首先从根节点开始,对输入实例的特征进行判断,并根据判别结果将实例分配至相应子节点,以此类推,直到对象到达叶节点。最终得到该实例所在类别。为提高决策树学习效率,常使用信息增益来选择特征。最早Farhi等人于1997年提出量子计算与决策树模型相结合的研究,其指出量子方法实现的决策树算法,在部分情况下相比于传统决策树算法更加高效[80]2014LuBrainstein提出了量子决策树分类器[81]LuBrainstein首先将样本数据( ) ( ){ }1,mk kkx y=转换成量子态{ }1,mi iix y=,其中( ) d kx R Î 为特征向量,d为特征维数,( ){ }1nkjjy C=Î 为所属类别。他们在选取最优特征时,将冯诺依曼熵作为判断依据,如式(26)所示。( ) ( ) = tr log S r r r - (26)其中1=nt ti i iip y y r= å 为第t个节点的对应类别量子态的密度矩阵,tiy 为在第t个节点第i类论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 11的量子态,n表示类的总数。然后,通过计算该节点t的冯诺依曼熵的期望值,如式(27)所示。( )( )( )( ) ,1=itt te i j i jjS pS r r=å (27)其中,it 表示该节点的子节点数。每个节点会产生不同的期望值,即( )( ) { } ,1dte i jjS r=,最后选取其中期望值最小的( )( ) ,te i jS r ,所对应的特征作为最优特征。算法具体步骤详见文献[81]。该量子算法与传统决策树算法的不同之处在于,其使用量子信息中的冯诺依曼熵,来替换经典信息中的香农熵,通过计算其期望值,进而计算特征值。图6决策树分类过程实例图[81]3.2.4量子神经网络人工神经网络是一种仿生计算模型,通过模拟生物神经网络的结构和功能而得名[82]。人工神经网络也是一种非线性的数据建模工具。该模型由大量节点构成,这些节点也称为神经元。层与层之间神经元根据不同的权重相连接,形成网状结构的模型,每层的神经元都含有一个激活函数。网络的第一层为输入层,最后一层为输出层,中间层为隐含层。如图7所示,该图为神经网络的一部分,是第i层节点到第i+1层第j个节点的连接示意图,网络中其他点的连接情况类似。图7中左侧节点{ }1 =nijjx为第i层的神经元,它们通过权重{ }1 =nikjkw i+1层的第j个节点相连,且11ni i ij kj kkx wx+==å 。f 为激活函数,通常为非线性函数,例如常见的sigmoid函数。图7的输出函数可表示为式(28)。( )1 i ij ijx f b+= + wx (28)神经网络的训练过程是,将特征向量输入网络,根据网络处理后的输出结果,优化以网络权重为参数的损失函数。其目的是,经过训练使网络输出结果与标签的误差最小。神经网络常使用反向传播(Backpropagation,BP)算法进行训练。该方法主要包含两个阶段:1)前向传播:根据式(28)计算规则,由输入层向输出层逐层计算;2)反向传播:计算输出层与标签的误差,对损失函数使用梯度下降进行最优化,从输出层向输入层反向更新网络中各层权值。每一个训练样本均进行一次向前计算和反向更新的操作,最终至网络收敛。图7神经网络示意图相关研究指出,人脑的信息处理过程与量子效应相关,并且生物神经网络的动力学特征与量子系统的动力学特征相似,故产生了量子理论与生物神经网络相结合的研究[83]Kak1995年,将神经网络和量子计算的概念相结合,首次提出量子神经网络计算[10]。同年,Menneer等人提出了量子衍生神经网络,传统神经网络需使用数据集对同一网络进行训练,从而找到适合不同模式的网络参数。而他则利用量子叠加性原理,对同一模式训练多个同构网络,得到不同模式对应的同构网络的量子叠加[85]Behrman等人于1996年,首先从数学形式上提出了量子点神经网络的概念[11]。他们发现基于量子点的时间演化模型能够完成神经网络中的前向或反向计算,之后他们从不同方面对量子神经网络做了一系列研究[84],[86],[87],[88]。同年,Toth等人提出了量子细胞神经网络,其将网络中每个细胞视为一个量子系统,并使用含时薛定谔方程来描述该量子系统的演化过程[12]1998年,Ventura等人结合量子理论中的叠加性原理,将网络的权重向量替换为希尔伯特空间中的量子态表示,对神经网络的训12 计算机学报 2017年练,即对应这些量子态的演化[13],同年他又提出了量子联想存储算法(quantumassociative memory,QUAM),其相比于传统存储有着指数级提升[90]1998年,Menneer的博士论文以多宇宙理论为切入点,系统的研究了量子神经网络的相关问题[91]1999年,Pribram等人指出可以使用量子理论来解释人脑的处理过程[93]。同年,Zhou等人将量子神经网络应用到了手写数字识别领域[94]2000年,Narayanan等人对不同结构的量子神经网络进行了研究,指出量子神经网络相比传统神经网络训练更加高效,但全量子结构的网络模型并非更优[95]。同年,Ezhov等人对量子神经网络进行了综述性研究[96];同时Matsui首次提出了通过量子比特作为神经元,使用量子旋转门和受控非门构造神经网络[14]2001年,Gupta发现可使用阀值电路(thresholdcircuits)构建量子神经网络,该方案相比传统方案需要更少的资源,同时他也证明该网络的计算本质上等同传统方法[92]。同年,Altaisky提出了一种物理上简单可行的量子神经网络,该量子神经网络的输入输出可用偏振光实现,网络的权重可用平面分束器实现[97]2002年,开始不断出现基于量子神经网络应用研究,例如Kouda等人使用三层量子神经网络应用于图像压缩,该方法相较于传统方法其压缩效率更优[99]2005年,他们又通过4位和6位的奇偶校验法验证了基于量子比特的神经网络优于传统神经网络[100]2006年,周日贵等人提出了仅适用单个神经元即可实现传统异或操作的量子神经网络,解决传统神经网络需两层才能解决的线性不可分问题[15]2007年,李盼池等人提出了一种量子自组织特征映射网络模型[103]。该模型有两层,包含输入层与竞争层,神经元由量子态表示,其通过计算样本量子态与相应权值量子态的相似系数来提取聚类样本所隐含的模式特征。2008年,Silva等人做了一系列无权重的神经网络模型的不同实现方案[59]~[62],[101],[102],同时也在2013年给出了不同类型量子神经网络模型的分析比较[104]Schuld等人对现有量子神经网路做了系统的比较分析[105]。他们指出量子神经网络的框架应满足三个条件:1)神经网络的输入和输出都必须是经过编码的数据,通常将输入输出的二进制串,编码至量子态上;2)量子神经网络必须表达基本神经计算的原理及结构;3)量子神经网络中的演化过程,必须服从量子力学规律,如叠加性、纠缠性等。但Schuld指出现今的量子神经网络方法无法完全满足上述条件,并提出了使用量子随机游走的方式构建人工神经网络的方法[16]。虽然量子神经网络模型的实现方式有很多,但大致可分为以下几类:基于测量的量子神经网络;基于量子点的神经网络;基于量子电路的神经网络;基于量子随机行走的神经网络;基于量子比特的神经网络等。l 基于测量的量子神经网络基于测量的量子神经网络最先由Kak提出,他将网络视为一个量子系统y,并将网络的权重视为该系统的可观测量µw(可观测量由厄米算符表示),则有该算符对应的本征方程µwy ly = 。网络权值的更新过程,即为对系统不断进行测量操作,找出本征值=1 l 所对应µw的过程。另外一种基于测量的方法来自于Menneer等人,其将整个神经网络的权值(存储多种模式),视为多个网络权值(存储一种模式)的叠加,识别某个特定模式即为通过测量操作,使权值的叠加态塌缩到该模式的对应权值上。由于Kak的研究使用线性算符µw来表征系统演化,而传统神经网络的映射是非线性的,这两者是否等价还有待商榷。l 基于量子点的神经网络基于量子点神经网络的相关研究中,以Behrman的研究最具代表性。Behrman提出的神经网络与其他神经网络不同,整个网络只有一个神经元,网络权值的更新是通过该神经元在不同时间的状态变化来进行,并且可通过该方式实现传统神经网络的前向及反向传播计算。l 基于量子门的神经网络基于量子门电路的神经网络,其代表性方法是由MatsuiMaeda等人提出的[14],[98]Matsui使用一位量子旋转门及受控非门来构建神经网络,以量子态作为输入,根据传统前向传播算法提出了复数形式下的网络权值更新过程,其网络结构如图8所示。由于使用通用门来进行网络的构建,当网络复杂后,通用门的数量也会成倍增加,其并未考虑该构建方法是否为最优的量子门电路综合算法。论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 138基于量子门的神经网络l 基于量子比特的神经网络Kouda等人提出了使用量子比特10分别作为处于激活与未激活状态的神经元[100],并将神经网络结构定义为图9所示,周日贵等人也在该网络的构建方法的基础上进行了研究[15]。图9中 ( ) arguu 的相位角, ( ) gd 为Sigmoid 函数,( ) ( ) ( ) f =cos sinjij j ji eqq q q + = 。虽然Kouda的实验表明该模型好于传统神经网络以及复数神经网络,他认为该优势来自于量子的特有性质(如叠加性等),但他并未给出相应的数学证明。图9基于量子比特的神经元[100]3.3量子降维算法机器学习需要处理的数据特征通常是高维,特别是计算机视觉及自然语言处理领域。原始特征不但高维,而且包含了大量与学习问题相关度小、甚至不相关的信息。部分算法会随着维度的提高,出现高维空间中无法工作的情况。因此,降维操作在机器学习中十分重要。降维操作降低了数据复杂程度,剔除了不必要的无用信息,使模型能在降维之后进行有效的学习。经典机器学习常用的降维操作包括:主成分分析(principlecomponent analysis,PCA)[106],线性判别分析(lineardiscriminantanalysis,LDA[107],流行学习等,其中常用到的是PCA,该方法示意如图10所示。图10主成分分析示意图1近年来,也有研究人员着眼于将量子的叠加性、纠缠性原理同降维算法相结合,试图借助量子计算对高维数据处理的优点,以降低传统降维算法的计算复杂度。国外有Lloyd教授团队首次提出的量子主成分分析、Cong等人提出的量子线性判别分析,国内杨国武教授团队以及我们的研究小组,也在尝试通过量子方法解决高维数据降维问题。3.3.1量子主成分分析Lloyd等人在2014年提出量子主成分分析算法(QuantumprincipalcomponentanalysisQPCA)。由于量子系统的密度矩阵均为厄米矩阵,其可表示成Gram矩阵的形式,可看作是一组向量的协方差矩阵[26],因此该方法使用量子系统的多个密度矩阵副本构造对应特征值较大的特征向量。Lloyd指出QPCA也适用于量子态的判别。有两组量子态集合{ }1miif=和{ }1miij=,两组量子态的密度矩阵为1=i iim r f f-å 和1=i iim s j j-å 。判别新量子态c归属于哪组,可对量子态c进行密度矩阵连乘及量子相位估计操作,如式(29)所示。0j j jjx c c x ®å (29)其中,jx 为r s - 的特征向量,jx则为对应的特征值。对j j jjx c x å 的第二个量子比特进行测量。测量结果若为正,则判定为{ }1miif=集合,反之则为{ }1miij=。虽然QPCA对传统PCA具有一定加速作用,但是其假设使用QRAM对量子态进行制备[26],而QRAM至今被认为仅限于理论模型,并1http://www.nlpca.org/fig_pca_principal_component_analysis.png14 计算机学报 2017年未出现真正可靠的物理实现方案。3.3.2量子线性判别分析线性判别分析也可称为Fisher线性判别分析,该方法最先由Fisher1936年提出[108],通过计算类间数据散布度与类内数据散布度的比值,寻找最优区分数据的投影方向。其类间散布度bS及类内散布度wS 如式(30)(31)所示。( )( )1cNTb i iiS x x m m== - - å (30)( )( )1ciNTw i ii x cS x x m m= Î= - - åå (31)其中cN为类别个数,im为第i类数据的中心,x为数据集的中心,x属于类CiFisher判别函数为:( )TbTwwSwJ wwSw= (32)最佳投影方向为( ) J w最大的那个方向,即类间数据散布度尽可能的大,类内散布度尽可能的小。其等价于目标函数式(33),通过对该最优化问题的求解即可得到最优区分数据的投影方向wmax..   1TbTwTwwSwwSwst wSw=(33)2015,Cong等人受到HHL算法的启发,提出通过厄米矩阵连乘,来实现线性方程组求解的问题,并将其与线性判别分析结合,提出量子线性判别分析[109]。该方法同QPCA一样,都假设已有可靠的QRAM物理实现为基础,并以其能高效制备量子态为前提。Cong等提出的方法,首先使用QRAM制备态1y 和2y 。11110 01ccNicNi i iicQRAM iNx i x xNym m m==æ ö= ç ÷ç ÷è ø= - - -åå(34)21110 01MjMj cj j cj j cjjQRAM jMx j x xMym m m==æ ö=ç ÷è ø= - - -åå(35)然后通过这两个量子态的密度矩阵来表示bS wS ,即:21211ccNb i i iiNiiS x x xAA xm m mm=== - - -= -åå(36)21211cj iNw j i j i j ii x CMj cjjS x x xBB xm m mm= Î== - - -= -ååå(37)由于式(37)可通过拉格朗日乘子法求解后可得1w bS Sw w l-= 。令1/2bw S v-= ,通过量子相位估计得到v的特征值及特征向量。最后,通过厄米矩阵连乘求解得出最优投影方向w,具体步骤详见[109]。该算法与QPCA算法类似,都将原问题数据的协方差矩阵与量子系统的密度矩阵联系起来,之后对密度矩阵的特征值与特征向量进行研究,从而找出最优投影方向或主要特征向量。3.4量子深度学习量子深度学习最早由Wiebe等人提出[23],他们实现的是量子版本的玻尔兹曼机(restrictedBoltzmannmachine,RBM)。受限玻尔兹曼机最早由Hinton等人在1985年发明[110],并提出了该网络的快速训练算法[111],该算法使用能量函数来确定可视层和隐含层的联合概率分布。受限玻尔兹曼机结构如图11所示。论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 1511RBM网络结构图1网络中ijw为网络中可视层的第i个节点到隐含层第j个节点的权重, { }1niih== h 为隐藏层节点,{ }1mjjv== v 为可视层节点, { }1niic== c 为隐藏层偏置,{ }1mjjb== b 为可视层偏置。网络中输入输出的联合概率分布,服从Gibbs分布,如式(38)所示。( )( ) EePZ-=v,hv,h (38)其中v代表可视层单元,h代表隐含层单元,( ) EZ e-=åv,hv,h为归一化因子。式(38)中的能量E由易辛模型(IsingModel)给出,如式(39)所示。( )1 1 1 1n m m nij i j j j i ii j j iE whv bv ch= = = ==- - - åå å å v,h (39)学习问题为寻找网络参数{ } w,b,c ,在特定输入为{ }1mjjv=的情况下的最大化代价函数(40)。( )( )( )1, argmaxNiiL P== Õw,b,cw,b,cv v (40)( ) iv 代表第i个样本且假设服从独立同分布,由于处理乘积较为复杂,( ) Pv 为似然函数,故可将问题转化成等价形式,见式(41)。1http://image.diku.dk/shark/sphinx_pages/build/html/_images/rbm_graph( )()( )1 1ln , argmax ln2N Nii iL Pl= == - åÕTw,b,cw,b,cv v ww(41)2lTww为正规化项,作用是避免训练后出现过拟合问题。当网络为受限玻尔兹曼机时,代价函数对网络权重的梯度为:( )data modelln ,i j i j ijijLvh vh wwl¶= - -¶w,b,cv(42)其中 ( )data, f vh , ( )model, f vh 分别为:( )( )( )( ),,data, 1,traintraintrainEv hEv hv v hhf vhef vhN e--Î= ååå(43)( )( )( )( ),, model,,,,EvhEvhvhvhf vhef vhe--=åå(44)对于求解RBM代价函数的梯度估计及训练问题[20]Wiebe等人提出使用量子采样(GradientEstimationviaQuantumSampling, GEQS)及量子概率幅值估计[112](Gradient EstimationviaQuantumAmplitudeEstimation,GEQAE)两种算法。接下来,将针对于这两种算法详细介绍。3.4.1GEQS算法量子采样梯度估计算法,首先制备与网络输入及输出的概率分布相似的量子分布。使用平均场近似( ) Qv,h 有效地替代Gibbs采样。然后对制备的量子态进行测量操作,得到datai jvh modeli jvh 。最后根据式(42)计算得到权重梯度。算法中Gibbs分布的近似分布为式(45):( )( ) EMFMFePZ-=v,hv,h (45)令 ( )( )( )=MFnorm MFPPkZ Qv,hv,hv,hk为固定常数项,则有:( ) ( ) ( )normP Q P µ v,h v,h v,h (47)使用辅助量子比特将 ( ) ( )normP Q v,h v,h 编码至量子态的概率幅上,其中最后一位量子比特变换如式(48)所示。16 计算机学报 2017年( ) ( ) ( )1 , 0 , 1 0norm normP vh P vh - + ® (48)之后进行投影测量最后一位量子比特,若结果为1,则波包塌缩后到近似Gibbs分布。使用上述方法作用于模型的输入与输出,即可得到模型的Gibbs分布,最后计算可得模型的梯度。3.4.2GEQAE算法量子概率幅值梯度估计算法与GEQS大体思路相同,不同之处是:该方法量子态的制备使用QRAM来实现[24][25]。算法首先利用QRAM将训练数据转为量子态表示。1 11 10N Nii iU i i vN N = =æ ö=ç ÷è øå å (49)随后对式(49)所得量子态进行如式(48)的操作,可得式(50)。( ) ( ) ( )1, ,1,normhNi i i iiQv h h P v h i v v hNc=å å (50)最后datai jvh 则可通过式(51)得到,modeli jvh 同理。( )data= 1| 1i j i jvh Pv h c = = = (51)(51)中各项概率值,均可通过对式(50)相应的量子寄存器,进行量子概率幅值估计得到。最近Wiebe等人在通过量子方法解决RBM训练问题中得到启发,提出了新的量子RBM训练方法:InstrumentalRejectionSampling算法[113]。该算法相较于传统对比散度算法(contrastivedivergence,CD),拥有更加精确的梯度近似值[113]InstrumentalRejectionSampling算法用于目标函数的梯度进行近似。其思想源于GEQS算法,既然GEQS算法使用量子采样,是否存在对应的经典模拟,且尽可能的保留原有量子算法的优点。据此Wiebe提出了GEQS的经典模拟算法Instrumental RejectionSampling进行玻尔兹曼机的训练。这表示我们不仅可以通过量子计算机实现对传统机器学习的加速,还可借用量子物理的概念,抽象出数学模型,并将其与传统机器学习相结合,产生新的学习算法,如Horn2007年提出的量子聚类算法[17]Adcock等人在量子机器学习的研究报告中指出,除了现有方法,还有不少研究人员正尝试通过改变RBM的物理模型来解决问题[7]。例如将RBM使用的易辛模型换做海森堡模型,这是因为海森堡模型在考虑z轴自旋时,还分别考虑了x轴和y轴的自旋,这就使得模型更加具有鲁棒性;把Gibbs分布换做Bose-Einstein分布或Fermi-Dirac分布。这是因为Gibbs分布为经典机器学习系统中的分布,在量子效应未占主导时可用其进行分析,但当量子效应占主导则需考虑Bose-Einstein分布和Fermi-Dirac分布。3.5算法比较本节对具有代表性的量子机器学习算法,从时间复杂度、数据是否量子化、是否具有物理实现等方面进行对比分析,详见表1所示。表项中的量子化表示输入输出是否为量子态,是否涉及经典数据与量子数据的转换。表1列举出了目前量子机器学习中较为有代表性的工作。其中无监督学习算法和监督学习算法中大多都使用了Grover的量子搜索相关算法,例如K-mediansQuantumSVM等。此外,本领域研究论文很少提及相应算法在真实物理条件下的表现。其原因,一是,该领域属于交叉学科,部分偏重理论研究的作者,不具备物理实验背景及相关实验设施,故无法完成相关算法的物理实验。二是,不少研究基于QRAM进行初态的制备,但至今还未出现完美的QRAM物理实现,故无法给出算法的真实表现。量子机器学习算法对经典算法的加速主要来源于两类:1)经典算法思路不变,通过将处理数据量子化,借助量子计算机的高并行性进行快速处理。首先将经典信息转为量子态,其次输入量子计算机,之后运行相应量子算法实现,即可对其相应的经典步骤进行量子加速。2)借助量子原理,从算法思路上进行创新,借鉴物理演化过程,改变原有算法,对传统机器学习算法进行加速。若涉及使用QRAM进行经典数据和量子数据的转换,那都会将加速效果降为多项式时间的加速,如QPCAQuantumK-meansQSVM等。表格1量子算法对比算法名称 量子算法复杂度 经典算法复杂度 量子化 物理实现 参数说明QuantumWeightlessNeuralNetwork[62]— ( ) ( ) Opoly N 是 有 N为训练样本数论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 17Quantumk-nearstNeighbours[21]( ) ( ) log O nm ( ) Onm 否 否n为训练向量维度m为训练样本数QuantumPrincipleComponentAnalysis[26]( ) ( ) log O d ( ) Od 是 否 d为数据空间维度QuantumDeepLearning(AmplitudeEstimation)[23]( ) ( )2maxxxO NE k k +( ) ONEk 是 否N为训练样本数E为边的个数x为训练集QuantumDeepLearning(QuantumSampling)[23]( ) ( ) maxxxO NE k k +( ) ONEk 是 否N为训练集大小E为边的个数x为训练集QuantumK-means[18] ( ) ( ) log Ok kmn ( ) Omn 是 否n为训练向量维度m为训练样本数k为聚类簇总数QuantumSVM[22][40][78] ( ) ( ) log O mn ( ) Omn 是 有n为训练向量维度m为训练样本数k为聚类簇总数QuantumDecisionTreeClassifier[81]( )( )( )1 211n kdT Tn k-+-( ) ( ) Omnlogn 否 否n为训练向量维度m为训练向量大小1 2, TT为两个子过程时间,详见[93]QuantumK-meidans[19]2nOkæ öç ÷è ø3/2nOkæ öç ÷è ø否 否 k为聚类簇总数QuantumDivisivelustering[20] ( ) log On n( )2On 否 否 n为训练样本数4总结与展望量子机器学习是结合量子力学原理和机器学习的交叉研究领域,其研究意义和价值为:第一,利用量子计算的高并行性,提高机器学习面对大数据的处理、分析和挖掘能力,如Lloyd等人的研究[18];第二,借鉴量子力学原理,促进新型机器学习算法的产生,如Wiebe等人的工作[113];第三,借鉴传统机器学习算法,提出量子力学领域新的研究方法,如提出新的量子断层分析方法[68]。量子机器学习的研究与进展,给众多的研究者带来了无限的希望和憧憬。让大家感受到了量子计算的巨大威力,虽然这仅仅是量子计算能力的冰山一角,但是我们需要更加需要理性的看待它。因为,在通用量子计算机建造成功之前,量子算法还很难在实际应用中展现出其数据处理方面强大的能力。目前,量子机器学习还有如下问题需要突破:l 量子机器学习算法的发展还处于一个相当初级的阶段,并没有如传统机器学习领域较为完备的理论框架加以指导研究。使用量子特性进行机器学习算法的研究大多还处于理论阶段,只有少部分论文提及具体算法的实现及验证。虽然理论上已经证明量子算法对部分经典计算问题有着可喜的提速效果,但是大多算法并未在量子环境下运行,只能通过模拟的方法实现,故难以展现其真正的数据处理能力。l 经典信息到量子信息的转换研究中,大多数工作基于Lloyd等人提出的QRAM,将经典信息编码到量子概率幅。但Adcock等人指出QRAM在具体物理实现上仍有许多问题未能解决,例如量子的退相干效应,所以这种读写方案在实际中是很难实现的[7]。虽然有研究人员对QRAM进行了分析与改进,从不同方面进行了相关尝试[114][115],但依旧未做出能够有效存储任意量子态的QRAM方法的物理实现。18 计算机学报 2017年l 在量子机器学习算法的设计上,Adcock也指出将数据编码到概率幅上会导致产生巨大Hilbert空间[7]。由于从量子信息中提取出经典信息主要通过量子测量操作,巨大的Hilbert空间将导致量子测量难以提取出经典信息。近年来量子机器学习吸引着越来越多的科研团队(MIT Seth Lloyd, Oxford universityQuantumOptimizationandMachineLearninggroup)、企业(GoogleQuantumA.I. Lab, QuantumArchitecturesandComputationGroup)和个体研究者,该领域的研究不仅可以推动机器学习发展,提高机器学习的学习效率和学习精度,也可促进量子世界的繁荣发展。加之,大数据时代来临、人工智能方兴未艾,这些都是推动量子机器学习发展的内在动力。综上所述,未来量子机器学习的研究令人振奋,同时也充满挑战。参考文献[1]. KohaviR, FosterP.Special issueonapplicationsofmachinelearningandtheknowledgediscoveryprocess. Journal ofMachineLearning,1998,30(2):271-274.[2]. Hilbert M, López P. The worlds technological capacity to store,communicate, andcomputeinformation. science, 2011, 332(6025):60-65.[3]. Feynman RP. Simulating physics with computers. Internationaljournaloftheoreticalphysics,1982,21(6):467-488.[4]. ShorPW.Algorithmsforquantumcomputation: Discretelogarithmsand factoring//Proceeding of 35th Annual Symposium onFoundationsofComputerScience.SantaFe,USA,1994:124-134.[5]. Grover LK. Afast quantummechanical algorithmfor databasesearch//Proceedingsofthetwenty-eighthannualACMsymposiumonTheoryofcomputing.Philadelphia,USA,1996:212-219.[6]. WittekP. QuantumMachineLearning: What QuantumComputingMeanstoDataMining. Cambridge,USA:AcademicPress,2014.[7]. AdcockJ, AllenE, DayM, et al. Advances inquantummachinelearning.arXiv:1512.02900,2015.[8]. SchuldM, SinayskiyI, PetruccioneF. Anintroductiontoquantummachinelearning.ContemporaryPhysics,2015,56(2):172-185.[9]. Shor PW. Why haven't more quantumalgorithms been found?.JournaloftheACM,2003,50(1):87-90.[10]. KakS. Onquantumneural computing. InformationSciences, 1995,83(3-4):143-160.[11]. BehrmanEC, Niemel J, SteckJ E, et al. Aquantumdot neuralnetwork//Proceedings of the 4th Workshop on Physics ofComputation.Portland,USA.1996:22-24.[12]. TothG, Lent CS, TougawPD, et al. Quantumcellular neuralnetworks.SuperlatticesandMicrostructures,1996,20(4):473-478.[13]. Ventura D, Martinez T. An Artificial Neuron with QuantumMechanical Properties//Proceedings of theInternational ConferenceonArtificial Neural Nets andGeneticAlgorithms. Norwich, UK,1998:482-485.[14]. Matsui N, Takai M, Nishimura H. Anetwork model based onqubitlikeneuroncorrespondingtoquantumcircuit. Electronics andCommunicationsinJapan(PartIII: FundamentalElectronicScience),2000,83(10):67-73.[15]. ZhouR, QinL, JiangN. Quantumperceptronnetwork//Proceedingsof the 16th International Conference on Artificial NeuralNetworks-VolumePartI. Athens,Greece,2006:651-657.[16]. SchuldM, SinayskiyI, Petruccione F. Quantumwalks ongraphsrepresenting the firing patterns of a quantumneural network.PhysicalReviewA,2014,89(3):032333.[17]. Horn D, Gottlieb A. Algorithmfor data clustering in patternrecognitionproblemsbasedonquantummechanics. PhysicalReviewLetters,2001,88(1):018702.[18]. Lloyd S, Mohseni M, Rebentrost P. Quantumalgorithms forsupervised and unsupervised machine learning. arXiv:1307.0411,2013.[19]. Aïmeur E, Brassard G, Gambs S. Quantum clusteringalgorithms//Proceedings of the 24th International Conference onMachineLearning.,Corvallis,USA,2007:1-8.[20]. Aïmeur E, Brassard G, Gambs S. Quantum speed-up forunsupervisedlearning.MachineLearning,2013,90(2):261-287.[21]. Wiebe N, Kapoor A, Svore K M. Quantum algorithms fornearest-neighbor methodsfor supervisedandunsupervisedlearning.QuantumInformation&Computation,2015,15(3-4):316-356.[22]. RebentrostP,MohseniM, LloydS. Quantumsupportvectormachinefor bigdataclassification. Physical ReviewLetters, 2014, 113(13):130503.[23]. Wiebe N, Kapoor A, Svore K M. Quantumdeep learning.arXiv:1412.3489,2014.[24]. Giovannetti V, Lloyd S, Maccone L. Quantumrandomaccessmemory.PhysicalReviewLetters,2008,100(16):160501.[25]. Giovannetti V, LloydS, Maccone L. Architectures for a quantumrandomaccessmemory.PhysicalReviewA,2008,78(5):052310.[26]. LloydS, Mohseni M, Rebentrost P. Quantumprincipal componentanalysis.NaturePhysics,2014,10(9):631-633.[27]. HarrowAW, HassidimA, LloydS. Quantumalgorithmfor linearsystems of equations. Physical ReviewLetters, 2009, 103(15):150502.[28]. Childs AM, Kothari R, Somma RD. Quantumlinear systemsalgorithmwith exponentially improved dependence on precision.arXiv:1511.02306,2015.论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 19[29]. ServedioRA, Gortler SJ. Equivalences andseparations betweenquantumand classical learnability. SIAMJournal on Computing,2004,33(5):1067-1092.[30]. Aïmeur E, BrassardG, Gambs S. Machinelearninginaquantumworld//Proceedingsofthe19thinternational conferenceonAdvancesin Artificial Intelligence: Canadian Society for ComputationalStudiesofIntelligence.QuebecCity,Canada,2006:431-442.[31]. YooS,BangJ,LeeC, etal.Aquantumspeedupinmachinelearning:findinganN-bit Booleanfunctionfor aclassification. NewJournalofPhysics,2014,16(10):103014.[32]. WANGSH, LONGGL. Bigdata andquantumcomputation[J].ChineseScienceBulletin,2015,60(5-6):499-508.(inChinese)(王书浩, 龙桂鲁. 大数据与量子计算. 科学通报, 2015, 60(5-6):499-508.)[33]. Pudenz KL, Lidar DA. Quantumadiabatic machine learning.QuantumInformationProcessing,2013,12(5):2027-2070.[34]. Neven H, Rose G, Macready WG. Image recognition with anadiabaticquantumcomputer I. Mappingtoquadraticunconstrainedbinaryoptimization. arXiv:0804.4457,2008.[35]. NevenH, DenchevVS, RoseG, et al. Trainingabinaryclassifierwiththequantumadiabaticalgorithm.arXiv:0811.0416,2008.[36]. Neven H, Denchev VS, Rose G, et al. Training a large scaleclassifier with the quantumadiabatic algorithm. arXiv:0912.0779,2009.[37]. Neven H, Denchev VS, Drew-Brook M, et al. NIPS 2009demonstration: Binaryclassificationusinghardwareimplementationofquantumannealing//ProceedingsofNeuralInformationProcessingSystems2009.Quantum.Vancouver,Canada,2009:1-17.[38]. Neven H, Denchev VS, Rose G, et al. QBoost: Large ScaleClassifier Training with Adiabatic Quantum Optimization//Proceedings of 4th Asian Conference on Machine Learning.Singapore2012:333-348.[39]. CaiXD,WuD, SuZE, et al. Entanglement-basedmachinelearningona quantumcomputer. Physical ReviewLetters, 2015, 114(11):110504.[40]. Li Z, LiuX, XuN, et al. Experimental realizationof a quantumsupport vector machine. Physical ReviewLetters, 2015, 114(14):140504.[41]. Landauer R. Thephysical natureof information. Physics lettersA,1996,217(4-5):188-193.[42]. Moore, GE. Crammingmorecomponents ontointegratedcircuits,Electronics,1965,38(8):114-117.[43]. ZHOUZ,TUT,GONGM, etal.Advancesandprospectsinresearchonquantumcomputation. ProgressinPhysics, 2009, 29(2): 127. (inChinese)周正威, 涂涛, 龚明, . 量子计算的进展和展望. 物理学进展,2009(2):127-165..[44]. Benioff P. The computer as a physical system: AmicroscopicquantummechanicalHamiltonianmodel ofcomputersasrepresentedby Turing machines. Journal of statistical physics, 1980, 22(5):563-591.[45]. Bammann K. Statistical models: theory and practice. Biometrics,2006,62(3):943-943.[46]. Cortes C, Vapnik V. Support-vector networks. Machine learning,1995,20(3):273-297.[47]. AgrawalR, ImielińskiT,SwamiA.Miningassociationrulesbetweensets of items in large databases//Proceedings of the 1993 ACMSIGMOD International Conference on Management of Data.Washington,USA,1993,22(2):207-216.[48]. HintonGE, SalakhutdinovRR. Reducingthedimensionalityofdatawithneuralnetworks.Science,2006,313(5786):504-507..[49]. Sun ZJ, Xue L, Xu YM, et al. Overviewof deep learning.Application Research of Computers, 2012, 29(8): 2806-2810. (inchinese)(孙志军, 薛磊, 许阳明, . 深度学习研究综述. 计算机应用研究,2012,29(8):2806-2810.)[50]. BengioY. LearningdeeparchitecturesforAI[J]. MachineLearning,2009,2(1):1-127.[51]. LarochelleH, ErhanD,CourvilleA, etal.Anempiricalevaluationofdeep architectures on problems with many factors ofvariation//Proceedings of the 24th International Conference onMachineLearning.Corvallis,USA,2007:473-480.[52]. LeCunY,BengioY.Convolutional networksforimages, speech, andtimeseries. TheHandbookof BrainTheoryandNeural Networks,SecondEdition,1995,3361(10):1995.[53]. LiuJ, LiuY, LuoXL. Researchanddevelopment ondeeplearning.Application Research of Computers, 2014, 31(7): 1921-1930(inchinese)(刘建伟, 刘媛, 罗雄麟. 深度学习研究进展. 计算机应用研究,2014,31(7):1921-1930.)[54]. AaronsonS. Thelearnabilityof quantumstates. Proceedingsof theRoyalSocietyofLondonA:Mathematical, PhysicalandEngineeringSciences.2007,463(2088):3089-3114.[55]. ChengHC, HsiehMH, YehPC. TheLearnabilityof UnknownQuantumMeasurements.arXiv:1501.00559,2015.[56]. Servedio R A, Gortler S J. Quantum versus classicallearnability//Proceedings of the 16thAnnual IEEEConference onComputationalComplexity.Chicago,USA,2001:138-148.[57]. Servedio R A. Separating quantum and classicallearning//Proceedings of the 28th International ColloquiumonAutomata, Languages and Programming. Crete, Greece, 2001:1065-1080.[58]. Atici A, Servedio RA. Improved bounds on quantumlearningalgorithms.QuantumInformationProcessing,2005,4(5):355-386.[59]. OliveiraW, SilvaAJ, Ludermir TB, et al. Quantumlogical neuralnetworks//Proceedings of the10thBrazilianSymposiumonNeuralNetworks,Salvador,Brazil,2008:147-152.[60]. SilvaA, deOliveiraW, LudermirT.Aweightlessneural nodebased20 计算机学报 2017on a probabilistic quantummemory//Proceedings of the EleventhBrazilianSymposiumonNeural Networks. SaoPaulo, Brazil, 2010:259-264.[61]. daSilvaAJ, LudermirTB, deOliveiraWR. Ontheuniversalityofquantumlogical neural networks//Proceedingsof the2012BrazilianSymposiumonNeuralNetworks.Curitiba,Brazil,2012:102-106.[62]. Da Silva AJ, De Oliveira WR, Ludermir TB. Classical andsuperposed learning for quantum weightless neural networks.Neurocomputing,2012,75(1):52-60.[63]. Tucci RR. Quantumbayesiannets. International Journal ofModernPhysicsB,1995,9(03):295-337.[64]. MonrasA, BeigeA, Wiesner K. HiddenQuantumMarkovModelsand non-adaptive read-out of many-body states.arXiv:1002.2337,2010.[65]. ClarkLA, HuangW, BarlowTM, et al. HiddenquantumMarkovmodels and open quantumsystems with instantaneous feedback//Proceedingsof InterdisciplinarySymposiumonComplexSystems2014.Florence,Italy,2015:143-151.[66]. Guţă M, Kotłowski W. Quantumlearning: asymptoticallyoptimalclassificationof qubit states. NewJournal of Physics, 2010, 12(12):123032.[67]. BisioA, Chiribella G, DAriano GM, et al. Optimal quantumlearningofaunitarytransformation. PhysicalReviewA,2010, 81(3):032324.[68]. GrossD,LiuYK, FlammiaST,etal.Quantumstatetomographyviacompressed sensing. Physical Review Letters, 2010, 105(15):150401.[69]. FlammiaST, Gross D, LiuYK, et al. Quantumtomographyviacompressedsensing: error bounds, samplecomplexityandefficientestimators.NewJournalofPhysics,2012,14(9):095022.[70]. Nielsen MA, Chuang I L. Quantumcomputation and quantuminformation.UnitedKingdom:CambridgeUniversityPress,2000.[71]. Long GL. Duality quantumcomputing and duality quantuminformationprocessing. International Journal ofTheoretical Physics,2011,50(4):1305-1318.[72]. MacQueen J. Some methods for classification and analysis ofmultivariate observations//Proceedings of the fifth Berkeleysymposiumon mathematical statistics and probability. Berkeley,USA,1967,1(14):281-297.[73]. BuhrmanH, Cleve R, Watrous J, et al. Quantumfingerprinting.PhysicalReviewLetters,2001,87(16):167902.[74]. Arthur D, Vassilvitskii S. k-means++: The advantages of carefulseeding//Proceedings of the eighteenth annual ACM-SIAMsymposiumon Discrete algorithms. NewOrleans, USA, 2007:1027-1035.[75]. MurtaghF. Asurveyof recent advances inhierarchical clusteringalgorithms.TheComputerJournal,1983,26(4):354-359.[76]. Durr C, Hoyer P. Aquantumalgorithmfor findingtheminimum.arXivquant-ph/9607014,1996.[77]. Bishop CM, Nasrabadi NM. Pattern recognition and machinelearning.JournalofElectronicImaging,2007,16(4):9901.[78]. AnguitaD, RidellaS, RivieccioF, et al. Quantumoptimizationfortraining support vector machines. Neural Networks, 2003, 16(5):763-770.[79]. Li H. Methodof statistical learning. Beijing: Tsinghua UniversityPress,2012李航. 统计学习方法. 北京:清华大学出版社,2012.[80]. Farhi E, Gutmann S. Quantumcomputation and decision trees.PhysicalReviewA,1998,58(2):915.[81]. LuS, BraunsteinSL. Quantumdecisiontree classifier. Quantuminformationprocessing,2014,13(3):757-770.[82]. Zeidenberg M. Neural networks in artificial intelligence. UpperSaddleRiver,NJ,USA:EllisHorwood,,1990.[83]. PerusM. Neuro-quantumparallelisminbrain-mindandcomputers.Informatica(Ljubljana),1996,20(2):173-184.[84]. BehrmanEC, Chandrashekar V, WangZ, et al. Aquantumneuralnetworkcomputesentanglement.arXivquant-ph/0202131,2002.[85]. Menneer T, Narayanan A. Quantum-inspired neural networks.Department of Computer Science, Exeter, United Kingdom:UniversityofExeter,TechnicalReport,329,1995.[86]. BehrmanEC, SteckJ E, Skinner SR. Aspatial quantumneuralcomputer//Proceedingsofthe1999InternationalJointConferenceonNeuralNetworks.Washington,USA,1999,2:874-877.[87]. BehrmanEC, NashLR, SteckJE, et al. Simulationsof quantumneuralnetworks.InformationSciences,2000,128(3):257-269.[88]. BehrmanEC, SteckJ E. Aquantumneural networkcomputes itsownrelativephase//Proceedings of the2013IEEESymposiumonSwarmIntelligence.Singapore,2013:119-124.[89]. BehrmanEC, SteckJE, KumarP, et al. Quantumalgorithmdesignusingdynamiclearning. arXiv:0808.1558,2008.[90]. Ventura D, Martinez T. Quantum associative memory withexponentialcapacity//Proceedingsofthe1998IEEEWorldCongressonComputational Intelligence. The 1998IEEEInternational JointConference on Neural Networks Proceedings. Anchorage, USA,1998,1:509-513.[91]. Menneer TSI. Quantumartificial neural networks[PhDthesis].UniversityofExeter,Exeter,UnitedKingdomd,1998.[92]. GuptaS, ZiaRKP. Quantumneural networks. Journal ofComputerandSystemSciences,2001,63(3):355-383.[93]. PribramKH. Quantumholography: Isit relevant tobrainfunction?InformationSciences,1999,115(1-4):97-102.[94]. Zhou J, Gan Q, Krzyżak A, et al. Recognition of handwrittennumerals by quantum neural network with fuzzy features.International Journal onDocument Analysis andRcognition, 1999,2(1):30-36.[95]. Narayanan A, Menneer T. Quantum artificial neural networkarchitectures andcomponents. InformationSciences, 2000, 128(3):231-255.论文在线出版号No.62 黄一鸣等:量子机器学习算法综述 21[96]. EzhovAA, VenturaD. Quantumneural networks. FutureDirectionsforIntelligentSystemsandInformationSciences,2000,45:213-235.[97]. AltaiskyMV. Quantumneural network. arXivquant-ph/0107012,2001.[98]. Maeda M, Suenaga M, Miyajima H. Alearning model in qubitneuron according to quantumcircuit//Proceedings of the Firstinternational conference on Advances in NaturalComputation-VolumePartI.Changsha,China,2005:283-292.[99]. KoudaN, Matsui N, NishimuraH. Imagecompressionbylayeredquantumneural networks. Neural ProcessingLetters, 2002, 16(1):67-80.[100]. KoudaN,MatsuiN,NishimuraH, etal.Qubitneuralnetworkanditslearningefficiency. Neural Computing&Applications, 2005, 14(2):114-121.[101]. daSilvaAJ, deOliveiraWR, Ludermir TB. Trainingaclassicalweightless neural networkinaquantumcomputer.//Proceedings ofthe 2014 European Symposiumon Artificial Neural Networks,Computational IntelligenceandMachineLearning. Bruges, Belgium,2014:523-528.[102]. daSilvaAJ, deOliveiraWR, Ludermir TB. Weightless neuralnetwork parameters and architecture selection in a quantumcomputer.Neurocomputing,2016,183:13-22.[103]. Li P C, Li SY, Aquantumself-organization feature mappingnetworks and clustering algorithm. Chinese Journal of QuantumElectronics,2007,24(4):463.(inChinese)(李盼池, 李士勇. 一种量子自组织特征映射网络模型及聚类算法. 量子电子学报,2007,24(4):463-468.)[104]. dePaulaNetoFM, daSilvaAJ, Ludermir TB, et al. AnalysisofQuantumNeuralModels//Proceedingsofthe11thBrazilianCongressonComputationalIntelligence. Ipojuca,Brazil,2013.[105]. SchuldM,SinayskiyI,PetruccioneF.Thequestforaquantumneuralnetwork.QuantumInformationProcessing,2014,13(11):2567-2586.[106]. Wold S, Esbensen K, Geladi P. Principal component analysis.Chemometrics and Intelligent Laboratory Systems, 1987, 2(1-3):37-52.[107]. Izenman AJ. Linear discriminant analysis, Modern multivariatestatistical techniques. NewYork, USA: Springer NewYork, 2013:237-280.[108]. Fisher RA. The use of multiple measurements in taxonomicproblems.Annalsofeugenics,1936,7(2):179-188.[109]. CongI, DuanL. Quantumdiscriminant analysis for dimensionalityreductionandclassification. NewJournal of Physics, 2016, 18(7):073011.[110]. HintonGE, Sejnowski TJ. LearningandrelearninginBoltzmannmachines, in Parallel Distributed Processing: Explorations in theMicrostructureofCognition,D.E.RumelhartandJ.L.McClelland,Eds.Cambridge,USA:MITPress,1986:282317[111]. HintonGE, OsinderoS, TehYW.Afast learningalgorithmfordeepbeliefnets.Neuralcomputation,2006,18(7):1527-1554.[112]. Brassard G, Hoyer P, Mosca M, et al. Quantum amplitudeamplification and estimation. Contemporary Mathematics, 2002,305:53-74.[113]. WiebeN, KapoorA, GranadeC, et al. QuantuminspiredtrainingforBoltzmannmachines.arXiv:1507.02642,2015.[114]. HongFY, XiangY, ZhuZY, et al. Robust quantumrandomaccessmemory.PhysicalReviewA,2012,86(1):010306.[115]. ArunachalamS, GheorghiuV, Jochym-OConnor T, et al. Ontherobustness of bucket brigade quantumRAM. NewJournal ofPhysics,2015,17(12):123010.HUANGYi-Ming, bornin1991, Ph.D. candidate. Hisresearch interests include dataanalysis, data mining andquantummachinelearning.LEIHang, bornin1960, Ph.D.,professor, Ph.D. supervisor. Hisresearch interests include dataminingandembeddedsystem.LI Xiao-Yuborn in 1984Ph.D., associatedprofessor. Her research interests include dataanalysis, quantum computation and quantummachinelearning.BackgroundQuantummachinelearningisanemergingfieldbetweenmachinelearningandquantumcomputation. Inthepasttensofyears, researchers try to investigate whether quantumcomputationcandosomehelpforimprovingclassicalmachinelearningalgorithms. Theirworksinclude1)Takeadvantageofthehighparallel of quantumcomputationtospeedupsomeconventional machine learning algorithms. 2) Use machinelearning algorithms to overcome fundamental quantumproblems. 3)Proposeanewideaofquantummachinelearningwhichisderivedfromprincipleofquantummechanics. Before22 计算机学报 2017theuniversal quantumcomputercomesintobeing, it ishardtohighlight the enormous power of quantumalgorithms. Inaddition,therearestillsomeproblemsandchallengesthatneedtobesolved.联系方式:黄一鸣15228881164;李晓瑜18108198701

[返回]
上一篇:集成测试中的类测试顺序生成技术述评
下一篇:基于数据库日志关联规则挖掘的业务流程优化