量子机器学习算法综述.pdf

所需积分/C币:47 2019-08-20 10:25:03 2.12MB PDF
309
收藏 收藏
举报

机器学习在过去十几年里不断发展,并对其他领域产生了深远的影响.近几年,研究人员发现结合量子计 算特性的新型机器学习算法可实现对传统算法的加速,该类成果引起了广泛的关注和研究.因此,文中对近十年的 量子机器学习算法进行总结、梳理.首先,介绍了量子计算和机器学习的基本概念;其次,从四个方面分别介绍了量 子机器学习,分别是量子无监督聚类算法、量子有监督分类算法、量子降维算法、量子深度学习;同时,对比分析量 子机器学习算法与传统机器学习算法的区别和联系;最后,总结该领域存在的问题及挑战,并对量子机器学习未来 的工作进行展望.
期 黄一鸣等:量子机器学习算法综述 147 其应用到机器学习领域,解决目前处理大数据时计深度学习相结合其通过量子采样实现受限玻尔兹 算效率低的问题 曼机的梯度估计,旨在加速深度网络的训练21.上 近年来岀现越来越多结合量子计算和机器学习述量子机器学习算法的核心大多还是与传统算法相 的硏究.研究人员一方面希望通过量子计算解决同,主要区别在于通过量子计算的高并行性去处理 机器学习的运算效率问题;另一方面探索使用量子计算耗时的子步骤 力学的性质,开发更加智能的机器学习算法.虽然量 其他关于量子计算及机器学习核心问题的研究 子计算机的研究不断深入,但依然有不少问题有待也进一步推动量子机器学习的发展.首先, Giovannetti 解决,例如如何保持量子的相干性、如何降低苛刻等人于208年提岀了量子随机存取存储器( Quantum 的环境条件等同时,量子计算机的建造以及量子算 Random access memory,QRAM)2,随后许 法的提岀都涉及诸多领域要素,量子机器学习理论多量子机器学习算法相继产生,如2014年 Lloyd 现在依旧处于一个起步阶段,至今没有形成如经典等人基于QRAM提出量子主成分分析( Quantum 机器学习领域完备的理论体系,大多研究还处于探 Principle component Analysis,QPCA)算法等 索实验阶段 其次, Harrow等人于2009年,提出用量子算法解决 量子机器学习领域的研究最早可追溯到1995线性系统的方程问题,常被研究人员成为HHL 年对量子神经网络的研究:Kak最先提出量子神经算法;2015年, Childs等人也对该问题进行了相关 计算的概念.随后硏究人员提出了各类量子神经研究,进一步拓展了量子算法对线性系统问题 网络模型如Bε hrman等人提出的基于量子点神经的解决能力.很多传统机器学习问题最终与最优 网络模型11,Toth等人提出了量子细胞神经网化问题的求解相关,而最优化问题常涉及线性方 络, Ventura等人提出的使用量子叠加态表示网程组的求解,所以通过该技术可有助经典机器学 络, Matsui等人提出了通过量子门电路实现的神习中最优化步骤的提速.例如, Rebentrost等人在 经网络,hou等人提出了量子感知机3, Schuld2014年提出的量子支持向量机就用到了量子线性 等人提出了由量子随机行走构建神经网络,等方程求解算法2.很多算法是以QRAM物理实现 等这些不同种类的量子神经网络模型的构建,均是为前提,利用QRAM实现任意量子态的制备继而 基于量子力学特性与不同数据结构的结合.该领域进行后续量子态计算. 研究的一个难点在于如何将神经网络的非线性映射 对于量子机器学习的可学习性及其与经典算法 结构同量子计算的线性变换结合在一起,即如何实的比较,也是研究人员的关注点之一.204年, 现神经网络的量子演化 Servedio等人对传统机器学习算法的可学习性与量 研究人员发现量子特性有助于研究无监督聚类子算法的可学习性进行了分析与比较.随后, 问题故提出了量子无监督聚类算法.2001年,Horn2006年, Incur等人提出了在量子环境下完成机 等人最早将量子力学特性引入传统聚类算法其将器学习任务的猜想0.Y00等人从二分类问题上对 薛定谔方程与 Parzen窗估算量的极大值求解联系量子机器学习与传统机器学习进行了比较,指岀量 起来,用于发现数据的聚类中心η.2013年, Lloyd子的叠加性原理使得量子机器学习算法运算效率明 等人将量子态的叠加性应用到经典向量表示上,提显优于传统算法,并从茡习的接受域上进行了比较, 岀量子 K means算法,该算法理论上能够实现海量发现量子机器学习的接受域较大,从而决定了学习 数据的高效聚类.同年, Airmleur等人提出了量子效率优于传统算法3.随着大数据时代的到来,传 分裂聚类算法,其借助 Grover变体算法进行子过程统算法对于海贔欻据的处理能勹,也日益捉襟见肘 中最大距离的快速搜索.类似还有研究人员结这就进一步促使研究人员考虑量子机器学习对大数 合监督分类算法和量子计算,提岀量子有监督分类据问题的解决能力和可行性.首先,2015年初陆朝 算法,例如Σl4年,微软的 Wiebe等人提岀了用量阳教授研究小组的相关研究开始关注量子机器学习 子态的概率幅表示经典向量,并通过比较两个量子与大数据的结合.随后,年底王书浩和龙桂鲁教 态间距离完成量子最近邻算法21.同年, Rebentrost授对量子机器学习及大数据领域的应用做了综述性 等人首次提出使用量子系统的密度矩阵进行支持向介绍.这些都进一步推动了量子计算在数据挖掘 量机中核矩阵的表示.2016年,微软的wicb等和数据分析方面的研究和应用 人提出了量子深度学习的概念,首次将量子计算同 以 D-Wave及 Google为首的公司对该领域也 148 计算机学报 2018年 进行了研究.2008年, Google的 Neven及 D-Wave示,也可由光的不同偏振方向来表示.一个量子态通 公司的Rose等人在其研发的超导绝热量子处理器常用狄拉克符号|来表示.数学上,它为一个n维 上使用量子绝热算法解决图像识别问题33,此后希尔伯特空间中的复向量,如式(1)所示 他们又做了一系列将量子绝热算法应用到人工智能 领域的研究33.这一系列量子绝热算法没有通过 Q;1 量子门电路进行量子计算而是运行在 D-Wave研式(1)中为基态,a为复数,是每个态的概率幅 发的特定量子芯片上,并且其运行的环境条件也相按照量子力学原理,如果测量该量子态g),最后会 对苛刻.目前他们研究的算法还有很多限制其商业以a:|的概率波包塌缩到基态|上,因此每个基态 领域的实际应用还有一段距离,不过已经向量子机的概率幅a必须满足式(2) 器学习的产业化应用迈出了坚实的一步 (2) 在量子机器学习的物理实验验证方面,全球的 研究人员也在努力不懈.2015年,潘建伟教授团队 多个量子比特组成的集合常称为量子寄存器, 首次在小型光量子计算机上实现并验证了 Lloyd提除了使用狄拉克符号也可以使用向量的形式表示 出的 K-means算法,Li等人也于同年实验验证例如可使用n维向量表示一个n位量子奇存器 了量子支持向量机算法,并进行了手写数字的二分 q)=∑a.|),如式(3)所示 类实验验证3.虽然实验的数据规模受限于当前量 子计算机的量子比特数,但足以证明量子机器学习 算法的可行性,且鼓舞我们在该领域进行更加深入 (3) 的研究,以获得解决海量数据分析处理的有用工具 相信随着制造工艺的不断提升,量子计算及量 子机器学习理论的不断完善,更多巧妙结合物理原其中每个基态|i)都可以展成二进制形式,如 理和机器学习理论的新型算法将被提出量子机器12-1)=11…12.11,…1)中1对应一位量 学习将极大促进现有机器学习的发展,产生出更加子比特 高效、强大的学习算法 21.2量子门 与经典计算机相同,量子计算机对量子比特的 2量子计算与机器学习 任何操作都可通过量子门实现.不同于经典计算机 进行门电路操作后产生的能量耗散.例如0和1的 21量子计算 与运算这是个不可逆且能量耗散的过程,量子计算 所有信息计算的本质都是一个物理过程.计机可通过幺正变换实现可逆计算,从而解决能耗上 算设备的物理特性决定其计算能力.根据 Moore定的问题.所以全部量子门都对应一个幺正算子.任何 律,集成电路上可容纳的晶体管数目约每隔位量子比特门都可用n×n的矩阵U来表示,如 24个月增加一倍.按此速度发展,一方面芯片元件式(4) 集成度的提高会导致单位体积内散热增加,由于材 料散热速度有限,就会出现计算速度的上限,产生 U=(u:)2 热耗效应”;另一方面元件尺寸的不断缩小,在纳米 甚至埃尺度下经典世界的物理规则不再适用.出现 因为U实质为一个幺正变换,则必须满足式(5) 尺寸效应”.综上,随着集成技术的提升,为解决条件 热耗效应”和“尺寸效应”不得不重新考虑能适用于 UU=UU=I 微观世界的新型计算机模型.由此量子计算应运而 生.它最早的想法源于Bmo提出的基于量子力学其中为U的共轭转置对量子态|y)=∑a|进 原理的可逆计算模型4,后来 Feynman进行了扩展 U变换,可得式(6) 21.1量子态 不同于经典电子计算机,量子计算机操作的基 liia li=∑B|i 本数据单元是量子比特( qubit).物理上,量子比特 可以有不同方法的实现,可由两能级原子系统来表 期 黄一鸣等:量子机器学习算法综述 149 算法等;随着研究的逐步深入,研究人员发现以上学 l!1 习算法具有一定的局限性.相对于深度学习,上述算 (6) 法的输入特征需要使用专业领域知识进行筛选提 取,同时该学习算法均使用单层非线性变换进行数 21.3测量 据分析处理.这种单层非线性变换结构制约了其对 量子计算的结果依旧处于一个叠加态为了得现实中更加复杂高维的函数的表示能力为了达到 到该结果必须对该量子态进行测量,使疊加态波包更好描述复杂世界,解决实际问题的目的,学习算法 塌缩到一个基态定义一组测量算子Mn},该组测需要拥有大量的训练数据作为基础使用专业的领 量算子还需满足完备性 域知识来提取优质的特征,通过强大的计算能力求 (7) 解问题.通常训练样本无法保证充足,同时特征的提 取也直接影响了学习算法的表现能力.因此,深度学 m对应测量的可能结果,若使用该测量算子对量子 态g)进行测量,最终得到m的概率为 习应运而生 p(m)=<nMnL) 深度学习的概念最早由 Hinton等人在2006年 (8) 测量后的量子态为 提出,文章指出多层的神经网络能更好地表达数据 本质,并且可以通过逐层初始化的方法解决多层复 M (9)杂网络训练困难的问题4.之后,不管是学术还是 PI MmMm c) 工业界,深度学习都引起了广泛的关注.大量的实验 22机器学习与深度学习 证明深度学习相对于浅层学习,精度上有明显的提 机器学习属于人工智能领域,主要利用计算机高不管从语音识别还是图像识别领域深度学习都 分析处理已知数据,从数据中自动“学习”潜在规则,能更好地刻画和承载海量数据中更丰富的信息典 并将此规则用于对未知数据的预测例如对手写字型的深度学习结构分为以下3种.(1)生成型,如 符的识别需要将字符图像信息转换成特征数据集深度信念网络.该类模型能表达输出与输入样本 X,X=(x,x3…,x,…x).数据集总共有数据间的联合概率分布解决网络初始权重设置问 m个样本,x为第i个样本x0=(x1,x2,…,题提升模型性能及收敛速度;(2)区分型如卷 x,…,x),每个样本有n个特征,x为第j个特积神经网络.该类模型使用权值共享,同一层神 征然后机器使用学习算法对手写字符集X进行潜经元共享一个权值集合,所以网络中的自由参数少 在规则的提取最后使用该规则进行字符的判断.传于传统网络;(3)混合型,该模型通过受限玻尔兹 统机器学习主要分为监督学习、无监督学习、半监督曼机预训练产生再使用反向传播算法( hackpropa 学习及增强学习.监督学习的训练样本都有人为标 gation algorithn,BP)优化深度信念网络的权值, 注分类结果的标签输入训练样本,通过最小化代价这样就比单用BP算法对卷积神经网络进行训练 函数,找出样本特征与标签之间的映射关系(学习模更优. 型)新的未标注数据通过训练得到的学习模型进行 分类无监督学习没有标注标签的训练集,学习算3量子机器学习 法自行寻找数据集当中的潜在规则,该类以聚类算 法最为常见.半监督学习是介于监督与无监督之间 量子机器学习借助量子计算的高并行性,实现进 的—种学习算法,为解决大数据量及监督学习标记 步优化传统机器学习的目的. Servedio, Aaronson 代价高的问题,其主要使用较少的带标签及较多的以及 Cheng等人对量子态的可学习性进行了研 未带标签数据进行训练分类.增强学习源于心理学究·. Servedio等人从信息论的角度指出量子 的奖励与惩罚,通过刺激进而逐步优化,通过不断的信息和经典信息的可学习性是等价的,这也促使了 反馈达到最优 量子机器学习研究的发展 3 Cheng 在 Scrvcdio 机器学习相较于以往基于人工规则的学习方法,的基础上提出量子学习算法主要分为两大类研 显示出强大处理分析能力各类学习算法不断被提究,一类是量子计算学习( Quantunnl Computational 出,例如通用的逻辑回归( Logistic regression, Learning,QCL),另一类是量子概率学习( Quantum IR)、支持向量机( Support vector machine,SWM)、 Statistical learning,QSL)2.QCI主要研究两点 关联规则挖掘( Associated Rules mining,ARM)(1)如何利用量子力学原理改进传统机器学习过 150 计算机学报 2018年 程,提高计算效率,降低计算复杂度823:5;(2)利版本运行在量子计算机上,从而得到提速该类研究 用统计学习理论去解决量子状态层析( Quantum的代表性成果有: Lloyd教授提出的QPCA、QsVM State Tomography,QsT)、寻找量子系统的隐藏结( Quantun Support Vector Machine)182等 构等问题.至今绝大部分前人工作都集中于解 决第一种计算复杂性问题.故本文主要介绍该类量 子机器学习算法 Learning Learning 并非所有经典学习算法的步骤都可通过量子特 性进行加速.量子力学公设指出封闭量子系统通过 TelAM 酉变换来刻画量子态的演化0,即量子态演化需要 由酉算子来实现.近年来,龙桂鲁教授研究小组提出 图1第一类量子机器学习 使用酉变换的线性组合,也可实现量子计算.量 子机器学习算法的基本原理是需将经典学习算法中 (2)第二类量子机器学习.该类算法的特点是 的信息映射成量子态,然后对量子态进行酉演化操寻找量子系统的力学效应、动力学特性与传统机器 作进而达到计算的目的因此,只有满足以上计算学习处理步骤的相似点,将物理过程应用于传统机 条件的经典学习步骤才能实现加速为使用量子特器学习问题的求解,产生出新的机器学习算法,如 性达到加速的目的就必须对传统算法进行相应的图2所示该类算法与第一类不同其全部过程均可 改写,使其满足上述量子计算的基本要求当前的研在经典计算机上进行实现在其他领域也有不少类 究大多集中于用量子算法替代原有经典算法的特定似以思路的研究如退火算法、蚁群算法等该类量子 子过程,进而达到降低计算复杂度提高算法效率的机器学习算法的代表性研究有Horm等人的基于量 目的. 子力学的聚类算法 量子机器学习算法一般需要经过以下步骤 步骤1.将经典信息转换成量子信息.为了发挥 Quantum Computation 量子计算机的高并行特性,必须对经典信息进行编 码,将其转换成量子信息,这就好比将一门语言翻译 Machine earniNg 为另外一门语言.合适巧妙的编码将更加有效的利 用量子计算的潜力 步骤2.传统机器学习算法的量子版转换.由于 图2第二类量子机器学习 量子计算机和经典电子计算机的操作单元不同,无 (3)第三类量子机器学习.该类算法主要借助 法将所有的经典计算机的方法都移植到量子计算机传统机器学习强大的数据分析能力,帮助物理学家 上,并且不是所有在量子计算机上的操作都会有指更好的研究量子系统更加有效的分析量子效应,作 数性的加速所以设计出适用于量子计算机的算法为物理学家对量子世界研究的有效辅助,如图3所 将十分重要量子机器学习算法的设计既要结合经示该类算法的提出将促进我们对微观世界进一步 典算法的数据结构数据库等技术·同时,还要不断的了解,并解释量子世界的奇特现象该类算法的代 设计出更多适合量子理论的算法模型这个建模的表性研究有:Gros的基于压缩感知的量子断层分 过程,也是步骤2的重点和难点 68-69] 步骤3.提取最终计算结果.由于计算结果为量 子态无法直接使用,需要经过量子测量操作,使量子 Machine 叠加态波包塌缩至经典态,将经典信息提取岀来. Learning 已有的量子机器学习主要可以分为以下3类 Quantum to explore Computation Quantum 分别是 World (1)第一类量子机器学习.该类算法将机器学 习中复杂度较高的部分替换为量子版本进行计算 图3第三类量子机器学习 从而提高其整体运算效率,如图1所示.该类量子机 器学习算法整体框架沿用原有机器学习的框架.其 由于量子机器学习的大多数研究集中于第一类 主体思想不变不同点在于将复杂计算转换成量子算法,第二类算法的研究还较少,第三类量子机器学 期 黄一鸣等:量子机器学习算法综述 151 习算法主要应用于物理领域.所以,本部分后续小节 1〈φ〉2通过 controlled-SWAP电路实现3 将着重介绍第一类量子机器学习算法.本文分别从如图4所示 无监督量子緊类算法、有监督量子分类算法、量子降 维算法、量子深度学习等几个方面进行,最后会对时 下主流的量子机器学习算法进行比较和分析 3.1无监督量子聚类算法 3.1.1量子 K-means算法 图4 controlled-SWAP量子电路实现 聚类算法是无监督学习算法中较为重要的 类.以最普遍使用的 k means算法为例,该算法以距 图4中H代表 Hadamard门,电路使能与否由 离的远近作为样本相似性指标,即两个样本的距离第一个量子比特控制,即电路最上面的量子线对应 越近相似程度就越高2.当涠到海量样本数据时,的是控制比特,下面的两个量子线对应的是受控量 k-means算法存在时间开销较大的缺点 子比特. controlled-SWAP电路作用于输入量子 Lloyd等人于2013年提出了量子版最近中心 g}和|必后,得到式(14) 算法量子最近中心算法可视为经典 k-means10)(1p>|)+1p)p)+1)( 类算法的子过程,使用该方法可对经典算法进行指 (14) 数级提速.该算法的加速来源于量子计算机具有对第一位量子比特进行测量得|0)的概率为 高维空间中对向量和张量操作的优势,这是由量子 P(0))=1+1 力学自身特性所决定的.量子力学使用希尔伯特空 间中的向量来描述物理系统而希尔伯特空间本身那么(4q)2=2P(O) 就是完备的线性空间,对量子态的操作即在线性空 k- IllegAls算法中初始点的选择十分重要,好的 间中对向量的操作同时,希尔伯特空间中的量子态初始点将极大地缩短迭代次数初始点选择的是否 满足叠加性原理对多个态可实行并行操作,故计算足够好,评判的一个标准是需要尽可能将初始点稀 效率远超经典计算量子计算满足以上量子力学规疏分布于整个样本空间中,即各点之间距离尽可能 律及数学特性,故量子机器学习能有效处理高维大为了优化初始点,Loyd使用量子绝热演化算法 数据量子最近中心算法的核心思想是对实向量间来实现kmen++算法最优初始点的选择.其 的距离作比较通过寻找向量n与集合(v}中的哪个基本思想为,首先初始化 Ilamiltonian量,如式(15) 量的距离最近,从而不断分类进而不断自动获得聚所示 (15) 类结果,即 arg.-mt·∑.Loyd通过 令4)=|g)8…②g,k为初始点个数,g 式(10)将实向量u=(l,t,…,ln)转换成量子态 u),从而将向量的距离比较转换成量子态间的距 m)∑1.φ)为样本标签编码后的归一化量 离比较 子态,m为样本总数然后定义未态 Hamiltonian如 (10) 式(16所示.未态 Hamiltonian的基态即是满足稀 疏分布的初始点·最后进行测量操作,提取基态信息 同时定义纠缠态g): 即可 1 )|0)+ vI)j (11) H 以及态|的 ul10∑v:|l (12) 在量子机器学习算法的物理实验方面,我国 的研究团队处于世界领先水平.2015年,潘建伟院 其中,a为实向量u的范数,ν>为c簇的第j个士团队以小型光量子计算机为实验平台,首次对 向量,m为样本总数,z=12+(n->v12)为归 Lloyd教授于2013年提出的量子K- rlledris算法进 行了物理实验验证.该实验将单光子作为一位量 化系数这两个量子态的距离可通过式(13)得到.子比特,使用自发参量下转换技术制备纠缠的光子 2(中|g)12z (13)对,并使用干涉仪将参考向量即测试向量编码到量 计算机学报 2018年 子态上.实验分别对4、6、8量子比特规模的算法进 该量子分裂聚类算法主要依靠 Grover变体算 行了验证,结果指出传统机器学习中普遍存在的高法来解决数据集的最值问题,相比于对应的传统算 维向量间距离和內积的计算可在量子计算机上实法,其提速效果主要源于此部分.该算法对传统分裂 现这表明量子计算机上实现的该部分运算其效率聚类算法的主体框架并未进行改变, Aimeur等人只 将优于传统算法,也预示着量子机器学习算法具有是将传统分裂聚类算法中计算复杂性较高的部分单 拥面向大数据分析处理的优势. 独提取出来,通过量子搜索算法进行提速.这种各取 3.1.2量子分裂聚类 所长的有机结合思路,也为后面众多的量子机器学 分裂分层聚类为聚类算法中简单常用的一类算习算法提供了很好的借鉴意义 法.该类算法,首先将所有数据点视为一个类然后32有监督量子分类算法 不断分裂类簇,直至每个类簇不能再分裂.其算321量子最近邻算法 法流程,通常初始选取所有数据点中尽可能远的 最近邻算法为传统机器学习算法中关于分类的 两个数据点,作为初始分裂的两个子类的代表,如 种简单且有效的算法.该类算法核心思想是,对· 式(17)所示;其次,计算其余所有点与这两个点的距个样本x,在特征空间中找出与该样本最邻近的k 离,根据离这两个点的远近进行分配;以此类推,直个点,然后根据这k个点的类别,使用分类决策规则 到每个类内部点的两两距离都小于某阈值,结束(例如多数表决)决定x所属类别 分裂 相较于传统最近邻分类算法, Wiebe等人采用 Dmax(Cr Cv)- max x-y (17)与 Lloyd相似的研究思路,提出了量子最近邻算 D表示类别C及C之间的最大距离若有 法1.首先他将经典信息中的非零数据编码到量子 个样本,每个样本维度为m,则传统算法计算该步骤态的概率幅值上,通过 controlled-SWae电路计算 的时间复杂度为O(n2).显然,若处理大量样本,且相应两量子态的内积来确定量子态之间的距离 维数较高的数据集时经典算法的计算效率就会较Wib等人通过式(18)、(19)对向量a和向量v进 低200年, Aimeur等人提出了通过结合量子计行编码,其中向量中非零特征使用负指数形式表示 算实现快速寻找最大距离点这个子步骤.该方2=ve",n=|tnle,为已知分类结果的 法的核心步骤是使用Dur等人于199年提出的向量,d为非零特征数 Grover变体算法,通过该算法提高寻找数据集中)= 距离最远的两点的计算效率,以下为该算法的核心1 2 dL Lt 流程思想. 0)+ 1〉 QuantuIn divisive clustering (D) (18) 输入:数据集D 输出:聚类后数据集D 1.If(D內数据点均满足距离相似性条件 ; 1〉 Return d (19) 4.初始化d-ax=0 Ja为特征值上界对4和|)进行 controlled SWAP操作后即可得式(20) Grover变体算法寻找最远距离点a,b (v)|2=(2P(|0))-1)al2r2s If d(a,b)>drax Wiebe等人也尝试使用两量子态的欧式距离来 dun=d(a, b) 判定其分类规则(详见文献[21]),但实验结果显示 s. While(存在d(a,b)≥a1m) 该方法相比于内积方法,迭代次数更多,精度也低于 hx∈D 将x分配到对应的类簇a或类簇b 内积方法.故而,量子欧式距离分类算法并未得到 12. End for 推广 13.将D分裂形成类簇D和D 32.2量子支持向量机 11. Quantum divisive clustering( D) 支持向量机( SupportⅤ ector machine,SVM), 15. Quantum divisive clustering(D, 在传统机器学习算法中,是一种重要的监督类线 16. End if 性分类算法,其思想是通过寻找最大间隔分类超平 期 黄一鸣等:量子机器学习算法综述 153 面进行分类,寻找最大间隔超平面问题可等价于x,·x;,且x1|x;)=(|x;|-x;)·(|x,|-x,),此时 式(21) 通过求密度矩阵x〉(x的偏迹即可得到归一化核 arg max mint(w(x)+b)}(2)矩阵 上式中w是超平面的法向量,b是偏置,x:为第i tr2(Ix>x) x1|x,|<x;|x)i) 个训练样本,;∈{-1,1}为该训练样本的标签, lw|-t(v2y(x,)+b)为样本点到超平面的距离若 tr(K) (24) 分类正确则(w2中(x)+b)>0,否则t(w3(x)其中,X·x=xx,(xx)通过该方法就使 b)<<0 量子系统同传统机器学习的核矩阵联系起来,由于 其中最接近分类超平面的样本点x,这些点量子态之间的演化运算具有高并行性,通过该方法 也称为支持向量针对于这些支持向量,需要寻找 即可完成传统机器学习中对应核矩阵计算的加速 个超平面使得这些支持向量到该超平面的距离最 Rebentrost等人也提出了量子版本最小二乘法支 大通过超平面的尺度变换可将问题转化为式(22,.持向量机( Least-Squares Support Vector Machine, LS SVM.他们将传统SⅤM分类问题转化为求解 arg min (22)式(25)的问题 s.t.t(w小(x)+b)≥1 F|b,d〉-y 寻找距超平面距离最大的支持向量,即一个优 (25) 化求解问题,故而可通过 Langrangian方法解决.通 分的低维特征(x,x)变其中,b为偏置,向量d的每个元素为支持向量距最 换成线性可分的高维特征k(x,x),再对高位特征 优超平面的距离,b,d〉即表示分类超平面,且 (b,d)=F(0,y),y=(y,y2,…,yM)为训练 进行分类,特征空间映射示意如图5所示 样本的标签,求解过程类似HHL算法7.F Input space Feature space I K+y K为核短阵,y为可接受误差权重 最后,分类任务即转化为使用 controlled-SWAP操 作来比较b,d)和输入样本|x〉的距离,从而得到 x>所属类别 量子支持向量机算法的物理实验也有一些进 图5SM特征空间映射示意图① 展,最近L等人通过核磁共振的方法,在物理上实 关于量子支持向量机算法的有关研究,最早是现了4量子比特的量子SvM,并对最基本的手 Anguita等人于2003年使用量子计算的方法,解决写数字6和9进行识别实验结果显示识别精度高 了SVM的训练效率问题.随后, Rebentrost等人达99,虽然实验样本较小但该实验显示出量子 在2014年提出量子版本的SVM,其核心思想是利 理论与机器学习算法结合的可行性. 用量子算法解决训练数据的内积运算问题(核方23量子决策树算法 法)22. Rebentrost等人首先将特征向量的各维特 决策树模型是一种描述对象属性或特征,并与 对象所属类别之间进行关系映射,所形成的树形结 征编码至量子态概率幅|x)=|x1·∑(x),j,构模型.树中每个节点代表一个对象,分为内部 其中N为特征维度,(x)为第;个特征向量的第;节点和叶节点即最后一层节点两种内部节点代 个特征,x|为特征向量范数其次,制备如下量子表对象的属性值,叶节点代表对象的类别决策树分 态,如式(23)所示 类过程,如图6所示.分类,首先从根节点开始,对输 入实例的特征进行判断,并根据判别结果将实例分 x>=(√Nx)-1·2x|i沙x:〉(23) 配至相应子节点,以此类推,直到对象到达叶节点 其中,N2=∑|x12,x为第个训练样本 Rebentrost 最终得到该实例所在类别.为提高决策树学习效率, 常使用信息增益来选择特征. 等人之后将核矩阵和量子系统的密度矩阵联系起 来.由于核矩阵的每个元素为向量间的内积K;= Chttp://www.statso:t.com/textbook/suPport-vector-machines 154 计算机学报 2018年 为第i层的神经元,它们通过权重{}=1与i1 youth middle aged senior 层的第j个节点相连,且x1+1=∑wx./为激活 student? credit rating? 函数,通常为非线性函数,例如常见的 Sigmoid函 数图7的输出函数可表示为式(28) fair excellent +b 图6决策树分类过程实例图 最早 Farhi等人于1997年提出量子计算与决 策树模型相结合的研究,其指出量子方法实现的决 策树算法在部分情况下相比于传统决策树算法更 加高效81.2014年Lu和 Braunstein提出了量子决 策树分类器 Layer j I u和 Braunstein首先将样本数据{x,y}=1 转换成量子态{|x},|y)}1,其中x∈R为特征 向量,d为特征维数,y∈{C,为所属类别 他们在选取最优特征时,将冯诺依曼熵作为判 图7神经网络示意图 断依据,如式(26)所示. 神经网络的训练过程是,将特征向量输入网络, S(p)=-tr(plogp) (26) 根据网络处理后的输出结果,优化以网络权重为 其中,p=>py)为第t个节点的对应类别量参数的损失函数其目的是,经过训练网络输出结 果与标签的误差最小.神经网络常使用反向传播 子态的密度矩阵1)为在第个节点第美的量子( Backpropagat,BP)算法进行训练该方法主要 态,表示类的总数然后通过计算该节点:的冯包含两个阶段:(1)前向传播.根据式(28)计算规 诺依曼熵的期望值,如式(27所示. 则,由输入层向输出层逐层计算;(2)反向传播.计 p: S(pi.;) (27) 算输岀层与标签的误差,对损失函数使用梯度下降 其中,表示该节点的子节点数.每个节点会产生不 进行最优化,从输出层向输入层反向更新网络中各 层权值.每一个训练样本均进行一次向前计算和反 同的期望值,即{S()}=,最后选取其中期望值向更新的操作,最终至网络收敛 最小的S(p),所对应的特征作为最优特征算法 相关研究指出,人脑的信息处理过程与量子效 具体步骤详见文献_80] 应相关,并且生物神经网络的动力学特征与量子系 该量子算法与传统决策树算法的不同之处在于,统的动力学特征相似,故产生了量子理论与生物神 其使用量子信息中的冯诺依曼熵,来替换经典信息 经网络相结合的研究.Kak于1995年,将神经网 中的香农熵,通过计算其期望值,进而计算特征值. 络和量子计算的概念相结合,首次提出量子神经网 3.2.4量子神经网络 络计算.同年, Mcnnccr等人提出了量子衍生神 人工神经网络是一种仿生计算模型,通过模拟经网络传统神经网络需使用数据集对同一网络进 生物神经网络的结构和功能而得名.人工神经网行训练,从而找到适合不同模式的网络参数而他则 络也是一种非线性的数据建模工具.该模型由大量利用量子疊加性原理,对同一模式训练多个同构网 节点构成这些节点也称为神经元层与层之间神经络,得到不同模式对应的同构网络的量子叠加 元根据不同的权重相连接形成网状结构的模型,每Bemi等人于1996年,首先从数学形式上提出了 层的神经元都含有一个激活函数网络的第一层为量子点神经网络的概念,他们发现基于量子点的 输入层,最后一层为输出层,中间层为隐含层 时间演化模型能够完成神经网络中的前向或反向计 如图7所示该图为神经网络的一部分,是第算之后他们从不同方面对量子神经网络做了一系 层节点到第+1层第j个节点的连接示意图网络列研究.同年,Toth等人提出了量子细胞神经 中其他点的连接情况类似.图7中左侧节点{x1 -1网络,其将网络中每个细胞视为一个量子系统,并使

...展开详情
试读 19P 量子机器学习算法综述.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
量子机器学习算法综述.pdf 47积分/C币 立即下载
1/19
量子机器学习算法综述.pdf第1页
量子机器学习算法综述.pdf第2页
量子机器学习算法综述.pdf第3页
量子机器学习算法综述.pdf第4页

试读结束, 可继续读2页

47积分/C币 立即下载