【深度解密】量子机器学习的研究进展

作者是来自英国布里斯托大学的量子工程中心研究员，布里斯托大学在量子力学和量子计算方面有很强的建树，诺贝尔物理学奖获得者、量子力学的奠基者之一保罗·狄拉克，中国科学院院士、固体物理学家、2001年中国最高科学技术奖获得者黄昆以及十余位诺贝尔奖得主均出自布里斯托大学。英国前首相丘吉尔曾长期担任该校校监（名誉校长），新古典经济学派的创始人阿尔弗雷德·马歇尔也曾在此担任校长。

名词含义

ANN：人工神经网络 Artificial Neural Network

BM：玻耳兹曼机 Boltzmann Machine

BN：贝叶斯网络 Bayesian Network

CDL：经典深度学习 Classical Deep Learning

CML：经典机器学习 Classical Machine Learning

HMM：隐马尔可夫模型 Hidden Markov Model

HQMM：隐量子马尔科夫模型 Hidden Quantum Markov Model

k-NN：k-近邻

NMR：核磁共振 Nuclear Magnetic Resonance

PCA：主成分分析 Principal Component Analysis

QBN：量子贝叶斯网络 Quantum Bayesian Network

QDL：量子深度学习 Quantum Deep Learning

QML：量子机器学习 Quantum Machine Learning

QPCA：量子主成分分析 Quantum Principle Component Analysis

QRAM：量子随机存取存储器 Quantum Random Access Memory

RAM：随机存取存储器 Random Access Memory

SQW：随机量子游走 Stochastic Quantum Walk

SVM：支持向量机 Support Vector Machine

WNN：无权重式神经网络 Weightless Neural Network

1 介绍

机器学习算法被用于提取有意义的信息以及对数据做预测。与其他技术不同，这些算法会根据输入的数据来建立并且（或是）更新它们的预测模型。这个领域的应用范围非常广阔，从垃圾邮件过滤到图像识别，无所不包，展现出了一个巨大的市场和深远的社会影响。

最近几年，量子信息领域有了一些进展，显示出了特定的量子算法可以带来相较于经典计算来说快得多的速度。有人猜测，将这些技术应用到机器学习领域的话，可能会产生相似的效果。这对于量子计算这个发展中的领域而言将是一个极大的鼓舞，并且可能最终会为现有的机器学习问题带来全新的、可实用的解决方案。对于量子计算和量子信息领域的概括介绍，参见引Nielsen和Chuang的《量子计算和量子信息（10周年版）》（Quantum Computation and Quantum Information: 10th Anniversary Edition）。

量子机器学习是横跨量子物理学和计算机科学的最新兴起研究领域，该领域旨在结合量子力学和机器学习方法。量子机器学习模型或者算法倾向利用量子信息（quantum information）的优势来改进经典机器学习方法，例如在量子计算机上开发昂贵的经典机器学习算法的高效实现方式。然而，量子机器学习也包括了相反的途径，即将经典机器学习方法应用到量子信息学理论中。

虽然量子机器学习在起步阶段，但是量子机器学习用量子计算的“并行”能力，满足了外界对使其为大数据提供解决方法的高度期待。由于谷歌和微软这样的公司对量子计算硬件和软件的投入，这个潮流被凸显出来。然而量子计算才刚刚起步，还需要更多的理论基础和坚实的研究成果，才能进一步成长为一个完整的学科（academic discipline）。

1.1 经典机器学习 Classical Machine Learning

机器学习算法几乎只被用于分类数据，或者按照用户定义的类别来分类、或者按照算法从数据内部结构中发现的规律来分类。假设有一个数据集

，其中每个x_{i} 都是一个定义为

的数据点。举例来说，这可能是一个有许多张图片的信息的数据集，每个图像都用它包含的像素数量或是一个区域内的色彩之类的参数来定义。数据分类可能就是将含有汽车的图片分作一类、不含汽车的分作另一类。机器学习算法的角色就是来获取分类规则。

概括地说，机器学习算法可以被分成三类：监督式、非监督式、以及强化学习。监督式学习有一个事先定义好的数据集X_{T} （也被称作一个“标记好的（labelled）”数据集），其中包含了已经被正确分类的数据点，在分类时产生了一组类别数据

，其中y_{i} 是数据点x_{i} 的类别。机器学习算法会读入Y 和X_{T} ，然后不断对内部参数做优化、直到达到最接近Y 的分类结果。一旦机器学习完毕，它就开始处理全新的、没有被标记过的数据X ，对X 进行分类、而不是学习。与此相反，强化学习是没有训练集的，取而代之的是，用户周期性地为机器对于没有标记过的数据所作的分类评判正误。评判结果会被输入算法/机器中，之后算法会对此进行学习。有一些时候，分类数据集并没有被事先定义（也就是说Y }不存在），这就属于非监督式学习的范畴了；这通常是由于数据集太大或是太复杂。这样的情况下，机器会寻找数据中内涵的天然结构。举例来说，假设有一个非常大也非常复杂的数据集（n,m>>1），数据集中的每个数据点都是一个高维数据空间中的向量。数据的复杂性可能会让用户无法在事前定义一个理想的输出或是学习方法，这让监督式学习和强化学习难以实施。然而，无监督式的聚类算法，比如k-平均（k-means），是可以使用的，它们会将数据划分到不同的类（cluster）中。这些类可以反映数据的不同特征之间的关系，并且之后在分类新的数据时能被用来作为分类标准。这种分析的一种应用在于市场研究，其中数据可以是一次市场调查的结果。用户的目标是根据有相似属性的消费者进行市场的细分，之后就能对相似的消费者策划相似的营销策略。

1.2 量子机器学习

量子机器学习（QML）碰到的第一个问题就是它的定义。我们打算通过许多例子来说明清楚机器学习与量子力学能怎样结合，以及我们是否会把这些视为QML。这是非常主观的判断，任何深度的理论含义都需要更进一步的明确说法。

根据Aȉmeur、Brassard和Gambs的观点，我们会把情景按照学习的种类进行划分。图1是学习种类的示意图。

图1：不同种类学习的示意图。在这里，“Q”和“C”分别表示量子计算和经典计算。实线代表在学习过中协议的最低计算要求（the minimal computational requirements of the protocol）。L2中的虚线代表有可能数据无需被经典地（classically）表征。

首先，我们来考虑一下经典情况，它被定义为类别L0。传统的经典机器学习（CML）被包括其中——经典的机器用经典的数据进行学习。同样被包括进去的还有经典机器对于来自量子系统的数据进行机器学习；已经有一些算法开始应用这类学习。第二个类别L1，我们将它标记为QML。在这个类别里，学习过程主要由经典计算来运行，只有一部分协议（比如特定的子程序）需要访问一台量子计算机。这也就是说，量子计算带来的提速直接来自于学习过程中的一个部分（比如，通过使用Grover或者Shor的算法）。与L0相比，我们把经典数据输入经典和量子兼具的算法归类到类别L1。在这里要说明的是，虽然只有一小部分的算法需要一台量子计算机来运算，整体处理上来说，在量子计算机上运行并不会有什么不利的影响，因为经典计算也可以由量子计算机来高效地完成。然而，可能使用一台量子-经典混合计算机会更加实际。在这两类情况中，协议需要细致地考虑到任何在量子计算过程中数据读入输出的限制。

我们将最后一类学习标为L2；这一类也被认为属于QML。这一类别的算法并不包含那些在经典计算机上也能运行得一样高效的子程序。就像之前两类中一样，输入数据和输出数据都可以是经典的。当然，你也可以想象到一些数据天然就是量子形式的例子（例子之一就是学习一个量子信道的噪声模型）。

1.3 机器学习算法的比较

图2：空间S和时间T在量子计算线路模型（circuit model）中的角色

为了理解QML可能带来的益处，必须要从速度和分类表现的角度对经典和量子的机器学习算法进行比较。在比较算法时，计算机科学家们会考虑两种典型资源：

l 空间，S：运行这个算法所需要的计算空间的大小。正式地来说，“空间”指的是需要的量子比特数量。对于S个量子比特而言，相关Hillbert空间的维度就是2^S。分清这两种数值（S和2^S）是非常重要的，因为它们有指数级的区别。

l 时间，T：训练模型、然后在特定误差范围内进行分类所需要的时间。正式地来说，“时间”指的是需要的操作数量，在量子线路模型中则可以用应用于量子比特上的连续门（consecutive gates）的数量来表示。

图2在量子线路图示中展示了时间和空间的意义。这些通常是以下变量的函数：

训练数据集的大小，n：提供给算法的训练集中数据点的数量。

输入数据集的大小，N：让算法进行分类的数据点的数量。

数据点的维度，m：每个数据点的参数的数量。在机器学习中，每个数据点通常都是一个向量，向量中的元素是各个意味着特征的数字。

误差，ℇ：算法对非训练集做出的分类中的错误比例。

要注意的是，不是所有算法都一定会根据以上这些变量而产生资源倍增的情况。比如，非监督式学习与n无关，因为不存在训练数据。图3是两种假设的算法在误差和训练数据集大小变化时消耗资源变化的情况，它们表现出了不同的收敛性。这被用来强调在对算法作比较时，本质上也是在比较算法所应用于的情况。在这里，对于哪一种算法更“好”的断言完全取决于你愿意接受什么水平的误差。另一件需要注意的事情是，并不是所有的算法在拥有无穷尽的资源时误差都会收敛到0。

图3：两种不同的算法中，分类误差的倒数随着训练数据集增大而产生的变化。

量子机器学习算法

有很多关于如何将经典机器学习适配到量子信息处理中的提议。

量子支持向量机（Quantum Support Vector Machines）

使用一系列已知的量子算法可以将支持向量机应用到量子计算机上。为了构建超平面分离分类问题中的数据集，二元形式（dual form）或者最小二乘形式（least squares formulation）的线性方程可以使用量子算法来解决线性方程组。因而，一个很重要的技巧是找到一个常规做法来构建一个密度矩阵，让其中的元素与核函数矩阵（kernel matrix）中的元素对应。

从最终状态中抽取信息可以通过量子主成分分析法（principal component analysis）来完成。对心输入的分类可以通过一个所谓的“交换测试（swap test）”来完成，在测试中两个量子态之间的重叠会被计算。量子支持向量机计算所需的时间主要依赖于特征空间（feature space）的维度对数和训练向量的总数对数，经典的解决方法所需时间依赖于多项式相关性（polynomial dependence）。第一个量子支持向量机实验已经被实现了。

量子聚类和k近邻算法

机器学习算法如k平均算法（k-means clustering）或者使用k近邻算法（k-nearest neighbours）的分类方法是以计算特征向量和选定的向量（识别最近的质心（cluster centroid）或者是最近的某个特征向量）之间距离为基础的。在量子计算机上实现这种以距离为基础的方法意味着首先要找到一种使用量子算法计算经典距离的方式。一个常见的想法是采用两个精心设计的wavfuctions函数 ⟨Ψ│φ⟩ 来测量量子态之间的距离。

最小的距离可以依据一个迭代的Grover搜索算法来获取。

以距离为基础的机器学习算法如非监督集群算法（unsupervised clustering）也可以通过绝热量子计算（adiabatic quantum computing）来实现。绝热量子计算改进了经典计算时间，从Lloyd的算法 Ο(Μ log⁡(ΜΝ) ) 到 Ο(κ log⁡(ΜΝ) ) ，（其中M表示N维数据向量的总数，k表示给定聚类的数量）。

第一个以距离为基础的量子机器学习算法的实验已经在一台光子量子计算机上进展到了8维，证明了监督式邻近算法（supervised nearest-neighbour algorithm）和非监督式k平均算法（unsupervised k-means algorithm）。

量子神经网络

量子神经网络最开始从一个不同的角度来讨论，即量子效应（quantum effects）能不能以及如何在大脑生理的神经网络中起作用。然而，这个讨论很快转移到一个纯计算的焦点上——量子形式的人工神经网络，这个方法在机器学习中举足轻重。量子神经网络很多想法自此之后被发表出来。量子机器学习一个有趣的方法是以Grover的搜索算法为基础的量子联想记忆模型（the quantum associative memory model）。然而，找到一个令人信服的方法来训练一个量子神经网络仍然是个开放给公众的难题。

对量子信息的机器学习方法

量子机器学习这个词也可以用于描述那些将经典机器学习算法应用到量子信息理论问题上的方法。例如，当实验者不得不处理量子系统上不完整的信息或者资源时，贝叶斯方法和算法学习概念（concepts of algorithmic learning）可以被卓有成效地应用起来。这包括了量子态分类、哈密尔顿学习（Hamiltonian learning）算法和学习未知酉变换等机器学习方法。

公司对量子机器学习研究的投资

不仅仅是学术界，领军IT公司也对量子机器学习影响未来技术发展的潜力很感兴趣。谷歌研究团队（Google Research）在2013年启动了其量子人工智能实验室，谷歌、NASA和高校空间研究协会（Universities Space Research Association，USRA）联合运营这间实验室。其中一个重要用于研究的设备就是饱受争议的D-Wave量子计算机。另外，微软似乎对这个话题也很感兴趣，并且微软研究院院长Peter Lee表示要“急剧”增加公司在量子计算方面的活动。

结论

机器学习和量子信息处理是两个很大的技术领域，在探索它们的交叉部分之前，必须对这两个领域都有相当的了解。到目前为止，大部分QML研究都来自于其中一个领域的专家，所以可能会有一些疏忽存在。QML领域最成功的那些进展都来自与CML专家和量子信息专家之间的合作，这种合作有非常大的价值。早期的结果凸显了QML的潜力，不仅对时间和空间资源有益处，也带来了更准确的分类。我们也想要强调一下，QML的研究会帮助指引CML的研究，因此研究QML是非常重要的，哪怕我们现在还没有硬件设备来对QML进行应用。

在QML的实际应用前景变得清晰之前，仍然有一些重要的问题需要克服。最主要的问题是如何将大量的任意向量（arbitrary vectors）高效地载入一台量子计算机中。解决方案可能会来自于QRAM的实现；然而，就像之前讨论过的那样，现在还不清楚QRAM是否有可能被制作出来。

尽管有这些局限，对于用量子系统进行学习的研究依然是有趣而激动人心的。想想这意味着什么吧——能够进行学习的量子系统可能会带来全新的量子算法。CML领域已经开始改变整个社会。任何能够为机器学习和它时而产生的出人意料的结果带来加乘的东西都应该得到探索。

论文目录

缩写列表

1 介绍

1.1 经典机器学习

1.2 量子机器学习

1.3 机器学习算法的比较

2 量子机器学习算法

2.1 神经网络

2.1.1 量子游走

2.1.2 深度学习

2.2 贝叶斯网络

2.3 HHL：解线性方程组

2.4 主成分分析

2.5 一种用于k-平均聚类的量子最近质心算法

2.6 一种量子k-近邻算法

2.7 其他值得注意的算法

3 实验实现

3.1 绝热量子机器学习

3.2 在光量子计算机上实现量子支持向量机算法

3.3 在4量子比特的量子模拟器上实现量子支持向量机

4 挑战

4.1 量子计算的实际操作问题

4.2 量子算法设计中早期一些常见的陷阱

4.3 量子随机存取存储器

5 结论

6 致谢

附录

A 量子感知器模型

A.1 感知器

A.2 量子感知器

A.3 讨论

B 量子支持向量机中的概率距离

C 各量子算法概述表