量子支持向量机QSVM（二）

文献[1]在进行QSVM算法分析时定义了一个常数$ϵ_K$，本质上是定义了一个条件数$κ_{eff} = \frac{1}{ϵ_K}$。令矩阵F的特征值为${λ_j}$，${|λ_j|}$最大不超过1。由条件数的定义可知，只有满足式子$ϵ_K ≤ |λ_j| ≤ 1$的特征值$λ_j$在计算时会被考虑在内。

此外，令$Δt = \frac{t_0}{T}$，其中T是phase estimation的时间步数（number of time steps），$t_0$是phase estimation的运行时间。

QSVM算法的误差主要由以下两个操作引起的：

由文献[3]可知，在第一步phase estimation中，为保证得到较好的结果，令：

$\tilde{\lambda_k}:=2\pi\frac{k}{t_0}$，

因此，这一步在计算λ时引起的误差由$t_0$决定，为：

$O(\frac{1}{t_0})$。

第二步controlled rotation实现的操作为$λ →\frac{1}{λ}$，这一步骤引起的误差为$O(\frac{1}{λ})$。

综合上述两步，error为：

$O(\frac{1}{t_0λ})\leq O(\frac{1}{t_0\epsilon_k})$

若 $t_0$取值如下：

$O(\frac{k_eff}{\epsilon})=O(\frac{1}{\epsilon_k\epsilon})$

则得到最终error为：$O(ϵ)$。

QSVM算法的运行时间主要由以下几个操作引起的：

第一步核函数的准备时间为$O(logMN)$；

第二步phase estimation的时间步数T为（具体分析参见文献[1]）：

$T=O(\frac{t_0^2}{\epsilon})$

将$t_0=O(\frac{1}{\epsilon_kϵ})$带入上式，综合上述两步，算法的运行时间为

$\tilde{O}(\epsilon_k^{-2}\epsilon^{-3}logMN)$

第三步中，QSVM考虑采用amplitude amplification提高算法的成功概率，即将算法迭代执行$O(κ_{eff})$次，其中$κ_{eff} =\frac{1}{ϵ_k}$，

因此，最终QSVM算法的时间复杂度为

$O(k_{eff}^3\epsilon^{-3}logMN)$

在文献[1]中，专门列举了一节Nonlinear support vector machines作为QSVM的补充。

SVM算法一个强大的应用在于处理非线性分类问题。前期介绍过，对于线性不可分的情况，可以通过映射实现低维度到高维度的转换，使其变成线性可分。即，在原始低维空间中无法执行SVM分类，把样本向高维空间做映射，在高维空间中便可以执行SVM分类。这里所说的映射主要涉及到的便是核函数的构造。通过核函数的展开和计算理论，可以巧妙的避免升维引起的计算复杂度的增加甚至是“维数灾难”。如何选择构造这样的映射函数，也是很有趣的问题。更多的可以参阅文献[2]。

文献[1]中列举了一个简单的核函数，为内积的d次方，如图1所示。该例或者任何多项式核函数可以通过图1中所示张量积的技巧进行量子计算。但对于其他类型的核函数（如径向基函数，二层神经网络核函数等），文中并未给出相应的方法。有兴趣的小伙伴也可以做深入的研究。

在QSVM中，除了前几期介绍的量子算法swap test、phase estimation、amplitude amplification，还应用了QPCA中的技巧。此外，还涉及到了经典机器学习中的一些概念。从这个算法可以看到，量子算法在加速经典机器学习算法时在应用范围上会存在一定的限制，如在Nonlinear情形下的核函数，并非所有的核函数都能找到有效的量子算法进行解决。

对QSVM算法有任何想分享的内容，欢迎留言约稿。咱们下期见~

参考文献：

注：作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆

本文原创，首发在《量子机器学习》微信公众号，欢迎关注。