量子SVM与凸损失函数：减少负边缘值点误差

由量子支持向量机最简单的形式可知，如果代价函数的参数离散化，可以在代价空间中进行穷举搜索【94】。最小值的搜索是基于Grover 搜索的一个变体【95】。

由于不需要依赖梯度下降这样的算法，目标函数可能是非凸的。量子支持向量机在这个公式中的真正优势是这种处理非凸目标函数的能力，这会带来更好的泛化性能，特别是当训练数据中存在异常值时。

凸损失函数对较大负边缘值点施加较大惩罚进行修正，同时这些点的分类错误远离边界。在进行实验验证的时候离群值和分类噪声会影响凸损失函数。而精心设计的非凸损失函数能避免这一缺陷。

由于绝热量子优化对于非凸优化来说是理想的【96】，因此将支持向量机看作适用于绝热量子计算机的二次无约束二进制（quadratic unconstrained bi⁃nary）优化程序。因为不涉及核矩阵的计算，且具有O（N2d）的复杂度。虽然搜索过程的复杂度降低了，但计算复杂度将仍由核矩阵的生成难度来决定。

如果用量子方法计算核矩阵，复杂度为O（M2（M+ϵ-1log N））。同时，当使用支持向量机的最小二乘公式时，在训练集上有可能得到指数加速。

算法基于三个理念：

（1）量子矩阵反演的速度很快【97】。

（2）稀疏矩阵的仿真是有效的【98】。

（3）非稀疏密度矩阵显示特征结构的速度与经典算法相比具有指数级的加快【99】。

为了求解线性公式10.13，

需要反解

矩阵反演算法需要将矩阵指数模拟为F。将F分解为F=J+Kγ，其中

是星图（stargraph）的邻接矩阵，且

利用李积公式，得到指数(www.xing528.com)

为了得到指数，稀疏矩阵J 和单位矩阵的常数乘易于模拟【98】。

另一方面，核矩阵K 不是稀疏的。这就是量子自我分析起作用之处：给定密度矩阵ρ 的多个副本，有可能按e-ipt 执行；类似于量子主成分分析（10.8）。通过点积的量子计算和对ORAM 的访问，得到规范核矩阵。

利用量子相位估计，得到特征值和特征向量。如果精度期望是ϵ，则需要此状态的n=O（ϵ-3）份副本。然后，将式10.13 中的y 表示在特征基中，反演特征值以得到线性方程的解∣b，α>【97】。

使用该算法，训练支持向量参数的总时间复杂度为O（log（Nd））。

核函数是受限的，而线性和多项式核易于实现。实际上，内积是直接在嵌入式空间中求解的。在这个框架中，径向基函数的内核更加难以实现。

O（log（MN））状态需要执行分类。这一步对结果是有利的，因为它对内核进行指数级压缩。然而这也是一个缺点，因为训练的模型不是稀疏的。支持向量机成功的关键是结构风险最小化，已学习模型不能过度拟合数据，否则其泛化性能会很差。最小二乘公式和它的量子变体不是稀疏的：每个数据实例都将成为一个支持向量。

量子SVM 算法如下：

步1 计算得到

步3 利用李积公式，得到了指数

步4 通过点积的量子计算和对QRAM 的访问，得到核矩阵

得到解∣b，α>

步6 利用线性可分∣b，α>进行线性划分得到分类结果。