量子机器学习综述

近年来, 机器学习一直是被关注和探讨的研究热点, 被应用到各领域并在其中起着重要作用. 但随着数据量的不断增加, 机器学习算法训练时间越来越长. 与此同时, 量子计算机表现出强大的运算能力. 因此, 有研究人员尝试用量子计算的方法解决机器学习训练时间长的问题, 量子机器学习这一领域应运而生. 量子主成分分析、量子支持向量机、量子深度学习等量子机器学习算法相继被提出, 并有实验证明了量子机器学习算法有显著的加速效果, 使得量子机器学习的研究展现出逐步走高的趋势. 对量子机器学习算法进行综述. 首先介绍量子计算基础; 然后对量子监督学习、量子无监督学习、量子半监督学习、量子强化学习以及量子深度学习5类量子机器学习算法进行介绍; 接着对量子机器学习的相关应用进行介绍并给出了算法实验; 最后进行总结和展望.

机器学习是人工智能的重要组成部分, 它研究的是如何让计算机实现自我学习, 从而拥有一定的“智能”. 从 20 世纪 50 年代至 21 世纪初期, 机器学习发展越来越快, 应用越来越广泛, 线性判别分析、人工神经网络、支持 向量机等一个个优秀的算法被提出. 机器学习被广泛应用于我们的生活中, 可以说生活在信息化时代的我们, 身边 存在着大量的机器学习产品. O(N) N 但是机器学习算法的训练复杂度通常都比较高. K 近邻、支持向量机等经典机器学习算法的时间复杂度均在 以上 ( 为样本数量), 尤其是深度学习对算力要求极高, 对于庞大的训练样本, 需要花费大量的时间进行训 练. 随着大数据时代的到来, 信息海量增长, 仅依靠计算机带来的高速运算对如此庞大的数据进行处理已经越来越 困难. 提高算法的效率已经成为机器学习领域重要的研究课题. 量子计算由于叠加、并行等特性大大提升了算法效率, 为解决一些计算困难问题提供了新思路. 20 世纪 80 年代, Feynman[1]最早提出了量子计算的概念, Deutsch[2]研究了图灵机的量子模型——量子图灵机. Shor[3]在 1994 年提出了对大整数进行因式分解的 Shor 算法, 相对于经典算法来说该算法能够实现指数级加速, Grover[4]在 1996 年提出了能够在无序数据库中找到复合条件的元素的 Grover 搜索算法, 相对于经典算法来说该算法能够实现平 方级加速, 这些算法充分体现了量子计算强大的能力. 1995 年, 文献 [5] 提出了“Qubit (量子比特)”的概念, 相对于 经典的“0-1”比特, 量子比特的存储性能达到了指数级的提升. 之后一些基础的量子算法被提出, 包括量子相位估 计[6]、交换测试[7]、HHL 算法[8]等. 这些算法为量子计算在各个方面的应用打下了基础, 尤其是量子机器学习 (quantum machine learning, QML) 领域. QML 是一个集量子力学和机器学习优势于一身的交叉领域[9−12] . 一些现有 的 QML 算法可以解决当前信息社会中数据量大、训练过程慢的问题, 在时间上提供指数级的加速. 由于量子机器学习算法是在机器学习的基础上形成的一个领域, 因此, 与机器学习算法类似, 根据算法的训练 方式和训练时输出的可用性, 量子机器学习主要分为监督学习、无监督学习、半监督学习、强化学习和深度学 习 5 种类型. 监督学习算法中的训练数据带有标注, 训练过程能够根据这些数据得到一个最优模型; 无监督学习 (也叫非监督学习) 与监督学习的不同之处在于数据都没有标注, 需要直接对数据进行建模; 半监督学习结合监督 学习和无监督学习的优势, 应用于只拥有少量有标注数据的情况; 强化学习是不需要预先给定数据的第 3 种学习 范式, 它通过与环境的交互进行学习. 深度学习是在上述 4 种机器学习算法的基础上发展起来的, 其网络结构层次 更深、更复杂. 量子计算和机器学习的结合最早出现在 1995 年, Kak[13]考虑到生物信息处理中存在量子效应, 理论上提出了 量子神经网络 (quantum neural network, QNN) 的概念. 此后 QNN 领域得到了关注. 2000 年, Ventura 等人[14]提出 了基于 Grover 搜索算法和纠缠神经网络的量子联想神经网络模型, 相对于经典算法来说, 该算法达到了二次加速. 参数化量子神经网络 (parameterized QNN, PQNN) 最初由 Matsui 等人[15]在 2000 年提出, 当时并没有得到重视. 但 是, 参数化量子线路 (parameterized quantum circuit, PQC) 能够在含噪中等规模量子 (noisy intermediate-scale quantum, NISQ) 设备上有效地实现. 随着 NISQ 的大规模应用, 基于 PQC 的量子神经网络成为近几年来被研究较 多的量子神经网络算法. PQC 的初始参数通常是随机生成的, 有时会引起梯度消失. 因此, 2019 年, Grant 等人[16]提 出了一种可避免梯度消失的模型, 进而可以有效地对量子神经网络进行训练. 随后, 量子生成对抗网络 (quantum generative adversarial network, QGAN)、量子玻尔兹曼机等模型被提出. 除了神经网络, 其他监督学习算法的量子版本也被提出. 2014 年 Rebentrost 等人[17]提出量子支持向量机, 与 经典的最小二乘支持向量机相比, 它表现出指数加速. Bishwas 等人[18]实现了量子多分类支持向量机. K 近邻作为 机器学习中一种常用的分类算法, 在高维特征空间上进行计算需要花费大量的时间, 2014 年, Wiebe 等人[19]提出 量子最近邻算法, 相对于经典算法, 该算法达到了二次加速. Chen 等人[20]利用 Grover 算法寻找最相似的 K 个样 本, 从而实现量子 K 近邻算法. 除了上述分类算法之外, 用于预测连续值的量子回归算法也被提出[21−23] . 无监督算法方面, 2007 年, Aïmeur 等人[24]提出了量子分裂聚类算法和量子 K 中位数算法. Hou 等人[25]在 2022 年提出了 K 均值聚类算法, 并将其应用于心脏病检测. 同年, 谱聚类算法被提出[26] . 此外, 量子降维算法也是 一类重要的无监督机器学习算法, 目前已经提出的算法包括量子主成分分析 (quantum principal component analysis,QPCA)[27,28]和量子奇异值阈值算法 (quantum singular value thresholding, QSVT)[29]等. 除此之外, 量子半监督支持向量机[30]、量子一分类技术[31]等量子半监督学习被提出, 量子强化学习[32−34]和量 子深度学习算法[35−37]也被提出. 表 1 给出了量子机器学习算法的分类及其对应的主要参考文献. 此外, 能够运行量子算法的量子计算机硬件也处在快速发展过程中. 2007 年, 加拿大的 D-Wave 公司研发出量 子计算机猎户星座. 该量子计算机仅能处理一些最优化问题, 与通用计算机相距较远. 尽管如此, 猎户星座的诞生 对量子计算机领域来说具有里程碑的意义. 此后, IBM 推出超导量子计算机 Eagle; 霍尼韦尔发布离子阱量子计算 机 H1; 谷歌推出量子计算机 Sycamore; 本源量子推出超导量子计算机本源悟源. 虽然目前已经有了很多版本的量 子计算机, 但是现在离通用的量子计算机还有一段距离, 目前 NISQ 设备是主流的量子计算机. 本文主要综述量子机器学习算法, 对量子算法和相应经典算法之间的复杂度进行对比, 并对相同类型的量子 算法进行分析比较. 第 1 节对量子计算基础知识和量子基本算法进行介绍. 第 2–6 节分别介绍量子监督学习算法、 量子无监督学习算法、量子半监督学习算法、量子强化学习以及量子深度学习 5 类量子机器学习算法. 第 7 节为 量子机器学习算法的应用. 第 8 节为实验. 第 9 节为对该文的总结和对未来工作的展望.