第七章量子支持向量机 支持向量机(support vector ●Class+1 ●Class-1 mach i ne,.SVM),在传统机器学习 O Missclassified 算法中，是一种重要的监督类线性 分类算法，其思想是通过寻找最大 间隔分类超平面进行分类。 Support Vector Machine(SVM)
第七章 量子支持向量机 支持向量机（support vector machine, SVM），在传统机器学习 算法中，是一种重要的监督类线性 分类算法，其思想是通过寻找最大 间隔分类超平面进行分类
SVM被提出于1963年，在二十世纪90年代后得到快速发展 并衍生出一系列改进和扩展算法，包括多分类SVM、最小二 乘SVM(Least-Square SVM,LS-SVM)、支持向量回归 (Support Vector Regression,SVR)、支持向量聚类 support vector clustering)、半监督SVM(semi- supervised SVM,S3VM)[8] 等，在人像识别(face recognition)、文本分类(text categorization)等模式 识别(pattern recognition)问题中有广泛应用
SVM被提出于1963年，在二十世纪90年代后得到快速发展 并衍生出一系列改进和扩展算法，包括多分类SVM 、最小二 乘 SVM（Least-Square SVM, LS-SVM ） 、 支 持 向 量 回 归 （ Support Vector Regression, SVR）、 支 持 向 量 聚 类 （ support vector clustering）、 半 监 督 SVM（semisupervised SVM, S3VM）[8] 等 ， 在 人像识别 （ face recognition）、文本分类（text categorization）等模式 识别（pattern recognition）问题中有广泛应用
y 寻找最大间隔超平面问题可等价于式 w·X+b=1 w·x+b=0 m向3w明 w·x+b=-1 6 60 上式中w是超平面的法向量，b是偏置，x,为第i 个训练样本，t,∈{-1,1为该训练样本的标签， wt,(w(x)+b)为样本点到超平面的距离。若 分类正确，则t(w(x)+b)>0,否则 (w(x)+b)<0
寻找最大间隔超平面问题可等价于式
其中，最接近分类超平面的样本点X:，这些点也称 为支持向量。针对于这些支持向量，需要寻找一个超 平面，使得这些支持向量到该超平面的距离最大。通 过超平面的尺度变换可将问题转化为式 argmin s.ttn（w(x)+b)≥1 在数学里面s.t.是subject to的缩写，受约束的意思
其中，最接近分类超平面的样本点 ，这些点也称 为支持向量。针对于这些支持向量，需要寻找一个超 平面，使得这些支持向量到该超平面的距离最大。通 过超平面的尺度变换可将问题转化为式 在数学里面s.t.是subject to 的缩写,受约束的意思
寻找距超平面距离最大的支持向量，即一个优化求解问题，故 而可通过Langrangian方法解决。通常引入核方法，将线性不可分 的低维特征（飞，x)变换成线性可分的高维特征飞(x,)，再对高位 特征进行分类，特征空间映射示意如图所示。 Input space Feature space SVM特征空间映射示意图
寻找距超平面距离最大的支持向量，即一个优化求解问题，故 而可通过 Langrangian 方法解决。通常引入核方法，将线性不可分 的低维特征 变换成线性可分的高维特征 ，再对高位 特征进行分类,特征空间映射示意如图所示
关于量子支持向量机算法的有关研究，最早是 Anguita等人于2003年使用量子计算的方法，解 决了SVM的训练效率问题。随后，Rebentrost等 人在2014年提出量子版本的SVM,其核心思想是 利用量子算法解决训练数据的内积运算问题（核方 法)
关于量子支持向量机算法的有关研究，最早是 Anguita 等人于 2003 年使用量子计算的方法，解 决了 SVM 的训练效率问题。随后，Rebentrost 等 人在 2014 年提出量子版本的 SVM，其核心思想是 利用量子算法解决训练数据的内积运算问题（核方 法）
Quantum Support Vector Machine for Big Data Classification Patrick RebentrostMasoud Mohseniand Seth Lloyd Research Laboratory of Electronics,Massachusetts Institte of Technology,Cambridge,Massachusetts 02139,USA Google Research,Venice,California 90291,USA Department of Mechanical Engineering,Massachusetts Institte of Technology,Cambridge,Massachusetts 02139,USA (Received 12 February 2014;published 25 September 2014) Supervised machine learning is the classification of new data based on already classified training examples.In this work,we show that the support vector machine,an optimized binary classifier,can be implemented on a quantum computer,with complexity logarithmic in the size of the vectors and the number of training examples.In cases where classical sampling algorithms require polynomial time,an exponential speedup is obtained.At the core of this quantum big data algorithm is a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product(kernel)matrix
对偶多项式是要求对Karush-Kuhn-Tucker多项因子 a=(a1,...,am) 求最大值 L-立法a 受到限制条件的约束 K=kG,)=元元 ∑1a;=0 yj0j≥0 kernel function
对偶多项式是要求对Karush-Kuhn-Tucker多项因子 求最大值 受到限制条件的约束
Rebentrost的步骤是： 1.先将特征向量的各维特征编码至量子态概率幅 x)=P·∑(x),》 其中W为特征维度 (x),为第ⅰ个特征向量的第j个特征 x为特征向量范数
Rebentrost 的步骤是： 1.先将特征向量的各维特征编码至量子态概率幅 其中 为特征维度 为第 i 个特征向量的第 j 个特征 为特征向量范数
2.制备如下量子态 x=(N)·∑xx) 其中N,=∑k，x,为第i个训练样本
2. 制备如下量子态