8.3.3 量子有监督学习
在机器学习中，有监督的学习指在事先已经确定所有类别以及每个类别的特征的情况下，构建模型对未来的新数据的目标属性值或类别进行预测。通常，事先已经确定的类别，即其特征，用一组带有标签的数据集来提供。有监督学习的目标是对带标签的输入数据集进行
分析、处理以及建模，从而用于预测未来实际生活中出现的不带任何标签的数据。“有监督”即指机器学习算法受到我们以提供带标签的学习数据集等方式的监督引导。机器学习算法需要分析输入数据并找到其中的规律和互相之间的关系，从而预测新数据。
利用量子叠加态的性质，我们可以把指数规模的经典数据压缩到少量的量子比特当中。虽然从物理理论上我们不可能从这些少量的量子比特恢复出原始数据，但是通常情况下我们并不需要训练数据的所有信息，而只是借助它们对新数据进行预测。于是通过小心地设计量子算法，在不违背物理原则的情况下，我们依然能对现有的机器学习算法进行指数级别的加速。在机器学习领域中，需要学习或者预测的数据通常都以向量的形式给出，而量子计算机的理论天然地使用线性代数来描述，所以有很直观的方法来把日常生活工作中产生的海量信息编码到少量的对数级别数量的量子比特当中。同时，相关的算法，诸如 HHL 等量子算法的理论已经比较成熟，所以我们可以借助量子计算机改良现有的机器学习算法，设计更加高效的机器学习算法，以应对愈发庞大的数据规模。
8.3.3.1 数据预处理
在生活工作中产生的数据一般是以向量的形式给出的，并且以经典的形式存储在经典计算机中，或者以量子态的形式存储在量子随机存取存储器中。为了利用上量子计算机的优势，我们需要把经典数据编码到对数个量子比特中。从经典信息到量子态的转换是进行这类量子计算的第一步。当初始数据是存储在量子随机存取存储器中时候，我们能够通过一次查询就并行地获得关于整个输入数据集的信息，此时构造目标量子态比较容易[12]。但是当原始数据存储在经典计算机中时，那么到量子态的转换就变成了最耗时最困难的部分。
8.3.3.2 量子有监督算法
Lloyd，Mohseni 与 Rebentrost 在 2013 年对使用量子计算机解决
有监督分类问题作出了初步探索[12]。考虑最简单的情形，输入数据集只分为两个标签类。
则给定一个新的需要预测的数据之后，一个通用做法是把该数据点分类到离它最近的标签类，且这里一个数据点和一个标签类的距离定义为数据点到该标签类中元素平均值的欧氏距离。显然这是一个简单且行之有效的方法，并且在经典计算机中，计算这两个平均值需要线性时间。在经典机器计算中的学习过程即为计算两个标签类的元素的平均值，需要的时间为线性。
在量子计算机中，由于整个训练数据集已经编码到对数个量子比特中，我们所求的距离仅为一个实数，所以完全有可能仅在着对数个量子比特上进行操作而得到我们需要的距离。此时时间复杂度应该为对数，对经典算法形成了指数加速。
Lloyd 等人证明了，若输入数据已经经过了预处理并且在量子随机存储器中，则仅用对数时间计算以上距离是可行的。为了计算一个数据点到一个集合中元素的平均值的距离，我们可以构建两个不同的量子态，这两个量子态的维数为集合中元素的数量，且它们的保真度恰好为我们所求的距离。进而用交换测试[111,112]去测量这两个量子态的保真度就可以得到该数据点到集合中元素平均值的距离。用这个算法分别计算该数据点到两个标签类的距离，就可以决定该数据点最终的分类。由于维度为数据规模的量子态只需要对数级别的量子比特就能实现，所以这个方法只需要对数时间复杂度。
注意到Lloyd 等人的算法还具有很好的隐私性，这是因为其对包含数据集的量子随机存储器的查询次数很少，只有对数次。虽然一次量子查询能得到关于整个数据的综合信息，但是一次查询能得到的信息量是有限的。由信息论和量子层析的原理我们知道，要复原整个数据集，至少需要线性时间把每个数据点查询一次。而对数次查询只能获得关于数据集的对数量级的信息。于是我们发现借助量子计算机运
行机器学习算法不仅能带来时空复杂度的指数级提升，还能额外得到对原始数据的隐私性的保护，即机器学习算法或者用户终端除了获得用于预测新数据的必要的信息量之外，只能额外获得很少的关于训练集内容的信息，从而无法窥探一些敏感信息。
下面介绍量子计算机下一些常见的有监督学习算法的实现。
1.支持向量机
支持向量机为解决有监督分类问题的一个强有力的工具。支持向量的主要思想是寻找两个将数据集按照所属标签分割的平行的超平面，并且最大化超平面之间的距离。此时，在平面上的数据点就称为支持向量。若给定的数据无法完全按照所属标签用超平面分开，则可以用核技巧将低维的不可分数据映射到更高维使得它们线性可分。 Rebentrost，Mohseni 与 Lloyd 运用 HHL 算法，构造了一个量子最小二乘支持向量机[11]。
在传统的经典计算机中，用支持向量机处理数据至少需要线性时间。Rebentrost 等人的算法借助量子计算机的优势，通过把指数级别的带标签数据编码到量子态中的方式，用少量的量子比特就能处理指数级规模的数据。
支持向量机需要处理的一个概念为核矩阵。核矩阵在包括支持向量机在内的许多算法中都至关重要[15,16]。支持向量机中很重要的一种核矩阵为线性核。按照定义，给定数据集中的两个数据，则它们的线性核就是它们的内积。注意到在 HHL 算法中，我们可以用相位估计算法，去把一个矩阵的逆作用到一个向量上。我们可以不仅仅局限于矩阵的逆，而是可以对该算法进行拓展，从而高效地进行所有的形如 uTLv 的内积。这里 u 和 v 为向量，L 为任一矩阵[12]。于是，运用 HHL算法以及处理内积的算法，通过对量子态当中所包含的带标签的学习数据进行处理，我们可以以量子态的半正定矩阵的形式，生成一组数据的核矩阵。同时，由于核矩阵是非稀疏的，Patrick Rebentrost 的算
法需要一套对非稀疏矩阵的量子态进行矩阵幂的算法[26]。最后，该算法也能应用到非线性核的支持向量机上，实现对非线性支持向量机的指数加速。
2.线性回归
回归任务考虑的问题是如何用理论模型去拟合实验得到的数据，这是所有学科，尤其是实验科学都会遇到的重要问题。在机器学习理论中，回归问题亦可看成是学习一个未知函数的问题：在已知一个函数的若干个数据点的情况下，去学习这个函数的具体形式。这些数据点可能会有误差和噪音，所以真实的函数一般无法完全拟合这些给定的数据点。一般这个函数的大致形式需要我们去猜测，比如它是一个线性函数或者是一个多项式函数。在确定好所使用的理论模型或者函数的大致种类之后，通常需要调整很多参数，去最大化地拟合实验数据。所使用的模型或函数往往随着研究的具体问题而变化，并无固定形式，但是我们一般可以使得模型或者函数值随着参数线性变化。例如，当猜测函数为有限维多项式函数时，我们需要调整的参数即为各个幂次的系数。此时，我们需要拟合的就是一个线性函数。在经典计算机中，可以使用诸如最小二乘法或者梯度下降之类的算法解决线性回归问题。在量子计算机中，由于量子态天然地用线性代数表示，且若干个量子态可以表示指数维度的线性空间，所以可以用量子物理的特性设计高效的量子算法解决线性回归问题。
在经典计算机的算法中，最小二乘法求线性回归任务的解可以用摩尔-彭若斯广义逆（Moore-Penrose pseudoinverse）给出[17]。摩尔-彭若斯广义逆将矩阵逆的概念推广到所有矩阵上。由于 HHL 算法[4]恰巧在某种意义上实现了量子态上的矩阵逆算法，所以 Wiebe，Braun和 Lloyd 通过对 HHL 算法改良，在 2012 年算法实现了量子态上的摩尔-彭若斯广义逆变换，设计了更加高效的量子算法[14]。这个算法的缺点是它只能把矩阵逆的结果即最小二乘法解线性回归得到的解
编码到一个量子态当中。为了从量子态当中提取到这个解的具体参数，还需要进行一些繁复的过程，比如使用量子层析算法，还原出这个量 子态的所有参数，而量子层析往往需要指数复杂度时间。虽然无法高 效取得最优线性回归的具体参数，他们给出了基于得到的量子态，去 预测这个回归模型的拟合度的算法。
Schuld，Sinayskiy 以及 Petruccione 研究了直接用量子计算机进 行预测的问题[18]。他们的结果规避了使用量子层析等开销巨大的方法 获取线性回归的具体参数：在一个量子态当中得到线性回归的解之后， Schuld 等人设计了算法，可以直接基于这个量子态对未来的数据进行 预测。当然，当描述一个线性方程的参数比较少时，存储量子态肯定 要比以经典形式直接存储一个线性回归模型的参数要困难得许多。王 郭明在 2017 年在直接计算线性回归模型的参数，而不是把参数编码 到量子态的问题上，取得了重要进展。在某些特殊的问题上，其设计 的改进版本的量子算法，可以在对数时间内直接获得用最小二乘法解 决线性回归任务的解[13]。不同于之前若干基于原始 HHL 算法的结果 [14, 18]，王郭明的结果基于 Childs, Kothari, and Somma 的改进版本的 HHL 算法[9]。
3.贝叶斯分类器
贝叶斯分类器是一类以贝叶斯定理为基础，通过学习已有数据和条件，去计算目标数据所属分类的概率，从而进行分类的算法，是解决分类问题的一个有力工具。
在经典计算中，常用的分类器有朴素贝叶斯分类器，二次分类器和线性分类器等。邵长鹏在 2020 年借助分块编码实现了用量子计算机对贝叶斯分类器算法的加速[19]。由于量子计算机能够在某种程度上并行地处理指数量级的数据，所以该结果上述提到的朴素贝叶斯分类器，二次分类器和线性分类器都能起到指数的加速效果。