第5章〓量子分类

分类算法是数据挖掘、机器学习和模式识别中一个重要的研究领域。它先根据已知分类标签的训练集分析出分类模式，再通过该模式对新输入数据的类别进行预测。分类算法主要包括决策树算法、贝叶斯算法、人工神经网络算法、K近邻算法、支持向量机算法等。

分类算法被广泛应用，随着信息技术的发展以及大数据时代的到来，目前需要处理的数据量越来越大、数据维度越来越高，运行算法所需要的代价越来越大。因此，迫切需要设计高效、快速的机器学习算法以满足各种分类任务的需求。

量子分类算法利用量子存储和量子并行性加速经典分类算法，相比于其他量子机器学习算法，量子分类算法的研究成果相对较多，本节主要介绍量子支持向量机、量子K近邻和量子决策树三种分类算法。

5.1量子支持向量机


支持向量机(Support Vector Machine，SVM)算法是一种常用的有监督机器学习算法，该算法在给定训练样本的基础上，找到一个超平面，将不同类别的样本分开。2014年Rebentrost等提出了能够实现指数加速的量子支持向量机(Quantum SVM，QSVM)算法，它是最小二乘支持向量机的量子版本。QSVM主要通过矩阵的指数化和相位估计等算法完成训练，最后进行分类。本节首先介绍支持向量机原理，然后介绍相应的量子算法。

5.1.1支持向量机原理

假设N个训练样本组成的数据集为


{(xi,yi):xi∈RM,yi∈{1,-1}}i=0,1,…,N-1(5.1.1)

式中：  xi为单个样本的M维特征向量，xi=(x0ix1i…x(M-1)i)T(i=0,1,…,N-1)； yi为第i个样本的类别。

分类的原理是找到一个超平面，将分属不同类别的样本分开。如图5.1所示，有很多的超平面(图5.1中的细实线)可以将两个类区分开。支持向量机的基本思想是从这许多的超平面中找到一个最优超平面wTx+b=0(图5.1中的粗实线)，使得两个类的最前沿(图5.1中的虚线)


图5.1支持向量机原理示意图


到超平面的距离2w最大。正好处在最前沿的样本称为支持向量。对所有标签yi=1的样本，wTxi+b>0； 对所有标签yi=-1的样本，wTxi+b<0。


因此，SVM的数学表达式为


maxw,b2w
s.t. yi(wTxi+b)≥1,i=0,1,…,N-1(5.1.2)

其等价形式为


minw,bw22
s.t. yi(wTxi+b)≥1,i=0,1,…,N-1(5.1.3)

式中：  w决定了超平面wTx+b=0的方向； b是位移，决定了超平面到原点的距离。


最小二乘支持向量机通过引入非负参数ξi，将式(5.1.3)转换为下列形式：  


minw,b,ξi12w2+γ12∑N-1i=0ξ2i
s.t. (wTxi+b)=yi-yiξi,i=0,1,…,N-1(5.1.4)

式中：  γ为正则化参数； 
ξi为松弛变量或者软边距，其作用是在一定程度上放松对分类样本的要求，允许部分样本点分类错误来换取模型更强的泛化能力。

由拉格朗日乘子法可得式(5.1.4)的对偶问题为


0eTeK+γ-1Ibα=0y(5.1.5)

式中：  α为拉格朗日乘子，α=(α0α1…αN-1)T； e=(11…1)T; I为单位矩阵； y=(y0y1…yN-1)T; K中包含所有的训练样本，其元素的形式不唯一，由核函数决定。Kij=xTixj为最简单的线性核，在后续的章节中，将介绍其他形式的核函数。

通过求解式(5.1.5)得到的b和α构成SVM的超平面。此时，对于待分类样本x来说，可以使用下式实现分类：  


y(x)=sign∑N-1i=0αixTix+b(5.1.6)

5.1.2量子支持向量机算法

现在主流的量子支持向量机算法是基于最小二乘形式的量子支持向量机，主要任务是使用HHL算法求解式(5.1.5)中的线性方程组，得到描述超平面的量子态|b,α〉，然后构造待分类样本x的量子态，并对其进行分类。本节介绍的量子支持向量机主要分为训练和分类两个部分，并给出复杂度分析。

1. 训练

训练量子支持向量机的线路图如图5.2所示。由图可以看到，其训练线路图与HHL算法的线路图基本相同。



图5.2训练量子支持向量机的线路图


为了使用HHL算法求解式(5.1.5)，需要按照HHL算法的要求，将矩阵F=0eTeK+γ-1I和(0,yT)T制备好。F以指数的形式模拟，即V=eiFt。向量(0,yT)T被制备进量子态中，再加上辅助量子比特组成量子态|ψ0〉，|ψ0〉为


|ψ0〉=|0〉|0〉l∑Ni=0ki|i〉(5.1.7)

式中：  ki为向量(0,yT)T的第i个元素； l取决于相位估计的精度和成功率。

经过HHL算法之后，其输出为|ψ1〉，即


|ψ1〉=∑Ni=01-C21λ2i|0〉+C1λi|1〉〈ui|k〉|0〉l|ui〉
=∑Ni=01-C21λ2i〈ui|k〉|0〉|0〉l|ui〉+∑Ni=0C1λi〈ui|k〉|1〉|0〉l|ui〉(5.1.8)

式中：  |k〉=∑Ni=0ki|i〉，|k〉中存储的就是(0,yT)T； C1为归一化常数。

最后对存储在第一寄存器中的辅助量子比特进行测量，当量子比特为1时，第三寄存器的量子态为


|ψ2〉=C1∑Ni=0〈ui|k〉λi|ui〉(5.1.9)


由HHL算法可知，除去归一化因子C1，式(5.1.9)中的量子态就是式(5.1.5)的解。将|ui〉写成标准正交基线性组合的形式，则式(5.1.9)可以写为


|b,α〉=1Cb|0〉+∑N-1i=0αi|i+1〉(5.1.10)

式中：  C为归一化因子。

2. 分类

上面得到了支持向量机超平面的量子态|b,α〉，下面对待分类样本x进行分类，其对应的量子态为|x〉。由式(5.1.6)可知，对样本进行分类，需要构造新的量子态得到b+∑N-1i=0αixix〈xi|x〉的符号。

根据超平面量子态|b,α〉和待分类样本|x〉分别构造下述量子态：  


|u～〉=1Nu～b|0〉|0〉+∑N-1i=0αixii+1〉|xi〉(5.1.11)
|x～〉=1Nx～|0〉|0〉+∑N-1i=0xi+1〉|x〉(5.1.12)

式中：  Nu～和Nx～为归一化因子，且有


Nu～=b2+∑N-1i=0α2ixi2，Nx～=1+N|x|2


使用哈达玛测试可得〈u～|x～〉，即


〈u～|x～〉=1Nx～Nu～b+∑N-1i=0αixix〈xi|x〉(5.1.13)


由于对辅助比特进行测量得到|1〉的概率P(1)=12(1-〈u～|x～〉)，因此当P(1)<12时，内积〈u～|x～〉>0，可将x分类为+1类； 否则，分类为-1类。

3. 复杂度分析

在量子支持向量机中，HHL算法是主要组成部分，HHL算法的复杂度为O(poly(log N))。此外，使用哈达玛测试求内积时需要运行O1ε次，才能以误差ε得到概率P(1)。因此，量子支持向量机的时间复杂度为Opoly(log N)1ε。

5.1.3量子核函数

线性核对于线性不可分问题的分类效果不佳。在经典算法中，解决这个问题的方法是使用核函数。核函数能够将样本从原始空间映射到一个更高维的空间，使得样本在这个高维空间中线性可分。在量子支持向量机中，量子核函数也起着同样的作用。本节首先介绍核函数原理，然后介绍量子核函数。

1. 核函数原理

式(5.1.5)中矩阵K的元素为Kij=xTixj，这是最简单的线性核。事实上，K的元素有很多种取法，下式为常见的多项式核：  


Kij=(xTixj)d(5.1.14)

式中：  d为多项式的次数。

此外，还有拉普拉斯核、高斯核等形式，具体的可参见文献［1］。

2. 量子核函数

本节介绍多项式核的量子形式。令|φ(xi)〉=|xi〉…|xi〉，则量子多项式核可以表示为


Kij=φ(xi)·φ(xj)
=〈φ(xi)|φ(xj)〉=〈xi|…〈xi|xj〉…|xj〉
=〈xi|xj〉…〈xi|xj〉=〈xi|xj〉d(5.1.15)

利用式(5.1.15)的技巧可以构造任意多项式核。

5.1.4实现

本实验利用量子支持向量机来对手写数字6和9进行分类。训练集为一个6和一个9，它们对应的二维特征向量分别为x1=(0.987  0.159)T和x2=(0.354  0.935)T，满足归一化，标签分别为y1=+1和y2=-1。测试集6和9的特征向量分别为x3=(0.987  0.160)T和x4=(0.352  0.936)T。

在本实验中，考虑偏置b=0的情况，令γ=2，则式(5.1.5)退化为


(K+2-1I)α=y(5.1.16)

由于训练集为x1=(0.9870.159)T和x2=(0.3540.935)T，则K=10.4980.4981，因此F=(K+2-1I)=1.50.4980.4981.5，约等于1.50.50.51.5； 对应y=1-1，归一化之后y～=121-1。如图5.3所示，U_gate实现了HHL算法以及训练样本的构造(式(5.1.11))，X_gate用于构造待分类样本(式(5.1.12))。U_gate包括三部分：  一是HHL算法初始输入态，即|y～〉=|0〉-|1〉2； 二是利用HHL算法求得(K+2-1I)α=y的解，在此过程中要模拟eiF4teiF2t，过程和HHL算法一样，具体过程可参考HHL算法，这里不再赘述； 三是将训练集数据制备到量子线路中，实现式(5.1.11)。



图5.3量子支持向量机线路图



值得注意的是，由于HHL算法的最后没有进行测量，得到的量子态为|1〉|b,α〉+|0〉|G1〉，其中|G1〉为式(5.1.8)中的量子态∑Ni=01-C21λ2i〈ui|y〉|ui〉，记为垃圾态。因此，式(5.1.11)变为|1〉|u～〉+|0〉|G2〉，|G2〉为垃圾态，此时量子态|u～〉和|G2〉都在量子比特q4和q5中，|1〉和|0〉都在量子比特q1中。由于


(〈1|〈u～|+〈0|〈G2|)(|1〉|x～〉)=〈u～|x～〉(5.1.17)

因此，为了得到〈u～|x～〉，在量子比特q4和q5上使用X_gate制备量子态|x～〉时，需要将q1的量子态制备成|1〉。


当输入待测数据为6(x3=(0.9870.160)T)时，由图5.4(a)可知，测量q0得到|1〉的概率为0.475<12，分类结果为+1，即分类为“6”，因此分类正确； 当输入待测数据为9(x4=(0.3520.936)T)时，由5.4(b)可知，测量q0得到|1〉的概率为0.524>12，分类结果为-1，即分类为“9”，因此分类也是正确的。



图5.4量子支持向量实验结果


量子支持向量机的代码如下：  


1.%matplotlib inline

2.from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

3.from qiskit import execute

4.from qiskit import Aer

5.from qiskit import IBMQ

6.from math import pi

7.from qiskit.tools.visualization import plot_histogram

8.

9.circuit = QuantumCircuit(6,6)

10.

11.#自定义U_gate

12.def U_gate():

13.circuit = QuantumCircuit(5)

14.#量子态制备

15.circuit.x(3)







16.circuit.h(3)

17.#hhl算法

18.circuit.h(1)

19.circuit.h(2)

20.circuit.cu3(-pi/2,-pi/2,pi/2,1,3)

21.circuit.u1(3*pi/4,1)

22.circuit.cx(2, 3)

23.circuit.swap(1, 2)

24.circuit.h(2) #iQFT

25.circuit.cu1(-pi/2, 1, 2)

26.circuit.h(1)

27.circuit.swap(1,2)

28.circuit.cu3(pi/8, 0, 0, 1, 0)

29.circuit.cu3(pi/16, 0, 0, 2, 0)

30.circuit.swap(1,2)

31.circuit.h(1)

32.circuit.cu1(pi/2, 1, 2)

33.circuit.h(2)

34.circuit.swap(1, 2)

35.circuit.cx(2, 3)

36.circuit.u1(-3*pi/4,1)

37.circuit.cu3(-pi/2,pi/2,-pi/2,1,3)

38.circuit.h(2)

39.circuit.h(1)

40.#添加训练数据

41.circuit.cry(0.32,3,4)

42.circuit.x(3)

43.circuit.cry(2.82,3,4)

44.circuit.x(3)

45.circuit= circuit.to_gate()

46.circuit.name = "U_gate"

47.c_U = circuit.control()

48.return c_U

49.

50.circuit.h(0)

51.#使用U_gate

52.circuit.append(U_gate(),［0］+［i+1 for i in range(5)］)

53.

54.#自定义X_gate

55.def X_gate():

56.circuit = QuantumCircuit(5)

57.circuit.h(3)

58.circuit.x(0)

59.circuit.ry(2.422,4)

60.circuit= circuit.to_gate()

61.circuit.name = "X_gate"

62.c_U = circuit.control()

63.return c_U

64.

65.circuit.x(0)







66.#使用X_gate

67.circuit.append(X_gate(),［0］+［i+1 for i in range(5)］)

68.circuit.x(0)

69.circuit.h(0)

70.

71.#测量

72.circuit.measure(0,0)

73.

74.#绘制线路图

75.circuit.draw(output='mpl')

76.backend=Aer.get_backend('qasm_simulator')

77.job_sim=execute(circuit,backend,shots=20000)

78.sim_result=job_sim.result()

79.

80.#绘制结果图

81.measurement_result=sim_result.get_counts(circuit)

82.plot_histogram(measurement_result)





5.2量子K近邻

K近邻是一种简单有效的有监督机器学习算法。K近邻从一个给定训练集中找到与待分类样本最邻近的K个样本，这K个样本中的多数属于哪个类，则待分类样本就划分到哪个类中。2020年，Basheer等给出了量子K近邻算法，原理与经典K近邻相同，不同之处主要是先利用量子算法计算样本之间的距离，再利用最大值搜索算法找到距离最近的K个样本。

5.2.1K近邻基本原理

图5.5给出K近邻原理示意图。训练样本有两个类别，分别用三角形和正方形表示。对于新输入的待分类样本(用圆形表示)，计算所有训练样本与待分类样本的距离，找到与待分类样本最近的K个邻居。当K=3时，邻居中包括2个三角形和1个正方形，因此分类为三角形； 当K=5时，邻居中包括2个三角形和3个正方形，因此分类为正方形。虽然K近邻是有监督学习方法，但是它不需要训练过程，直接根据待分类样本与所有训练样本的距离确定分类结果。



图5.5K近邻原理示意图


在K近邻算法中，当训练集、K值以及距离度量确定后，任何一个新输入的样本都会对应一个唯一的类别。其中两个样本之间的距离计算是量子K近邻中最重要的部分，此外使用量子算法寻找K个最近邻样本也是一项重要内容。

5.2.2量子距离

在特征空间中，两个样本点的距离是两个样本相似程度的度量。在经典计算方法中，常用的相似度计算方法包括欧几里得距离、汉明距离、向量内积以及余弦距离等形式。在量子计算中，样本信息存储在量子态中。两个量子态之间的距离度量方式有迹距离和保真度两种方式。迹距离并不常用，这里不再介绍。保真度是衡量两个量子态相似程度的常用方法，保真度越大，两个量子态越相似。

【定义5.2.1】对于两个量子态|u〉和|v〉来说，其保真度定义为


F(|u〉,|v〉)=|〈u|v〉|2(5.2.1)

即保真度是|u〉和|v〉内积的模的平方，因此交换测试是计算两个量子态保真度的有效方法。

5.2.3量子最大值搜索

上一节描述了两个量子态之间的距离度量方法，如何使用量子算法找到和待分类样本最近的K个样本呢？由于保真度越大，两个量子态越相似，因此需要找到距离中最大的K个值。本节给出搜索最大值的量子算法。

令T={T0,T1,…,TN-1}为含有N个元素的无序数据库，元素的下标为{0,1,…,N-1}。最大值搜索算法的目的就是找到下标i(i∈{0,1,…,N-1})，使得Ti=max{T0,T1,…,TN-1}。具体算法如下：  

第一步：  从{0,1,…,N-1}中随机选取一个下标z1。

第二步：  重复下列步骤O(N)次：  

(1) 定义函数：  


fz1(z2)=1,Tz2>Tz10,其他(5.2.2)


(2) 应用Grover搜索算法找到满足式fz1(z2)=1的下标z2。

(3) 如果测量能够得到z2，则用z2代替z1； 否则，不做任何改变。

第三步：  最终的z1就是使得Ti为最大值的下标i。

在该算法中，第二步要重复O(N)次，而第二步(2)中使用的Grover算法的复杂度为O(N)，因此该算法总的复杂度为O(N)。

5.2.4量子K近邻算法

量子K近邻算法需要计算待分类样本与所有训练样本之间的保真度，并找到最近邻的K个训练样本。本节给出量子K近邻的具体算法。

假设N个训练样本组成的数据集如式(5.1.1)所示。令{|xi〉:i∈{0,1,…,N-1}}是训练样本所对应的量子态，|x〉是待分类的样本。量子K近邻算法先使用K次最大值搜索算法找到和待分类样本最近邻的K个样本{|xi0〉,|xi1〉,…,|xiK-1〉}，再采用经典的多数表决规则对|x〉进行分类。

经典的多数表决规则这里不再单独介绍。下面主要介绍量子实现过程，也就是找到和待分类样本最近邻的K个训练样本。为此首先计算待分类样本|x〉和所有训练样本{|xi〉:i∈{0,1,…,N-1}}之间的保真度，然后找到和待分类样本最近邻的K个训练样本。

1. 计算保真度

在上述数据集中每个样本有M个特征(令M=2m)。如图5.6所示的过程能够将训练样本|xi〉与待分类样本|x〉之间的保真度存储在基态中。



图5.6将保真度存储在基态中的量子线路图


主要分为两步：  

第一步：  使用交换测试将保真度相关信息存储到振幅中。

首先制备初始态


|ψ0〉=|0〉l|0〉l|0〉|0〉m|0〉m|i〉(5.2.3)


使用黑箱W作用于第五寄存器和第六寄存器得到量子态


|ψ1〉=|0〉l|0〉l|0〉|0〉m|xi〉|i〉(5.2.4)

使用黑箱V作用于第四寄存器得到量子态


|ψ2〉=|0〉l|0〉l|0〉|x〉|xi〉|i〉(5.2.5)

使用交换测试ST作用于第三寄存器、第四寄存器和第五寄存器可得


|ψ3〉=|0〉l|0〉l12［|0〉(|x〉|xi〉+|xi〉|x〉)+|1〉(|x〉|xi〉-|xi〉|x〉)］|i〉
=|0〉l|0〉l|φi〉|i〉(5.2.6)

式中


|φi〉=12［|0〉(|x〉|xi〉+|xi〉|x〉)+|1〉(|x〉|xi〉-|xi〉|x〉)］


令


|φi0〉=|x〉|xi〉+|xi〉|x〉(5.2.7)
|φi1〉=|x〉|xi〉-|xi〉|x〉(5.2.8)

则|φi〉可以表示成量子振幅估计算法中式(3.5.1)的形式，即


|φi〉=(1+Fi)2|0〉|φi0〉+(1-Fi)2|1〉|φi1〉(5.2.9)

式中：  Fi=F(x,xi)。

这时保真度相关信息存储在振幅cos(πθi)1+Fi2和sin(πθi)1-Fi2中，接下来要把存储在振幅中的信息转移到基态中。

第二步：  利用量子振幅估计算法将保真度信息存储到基态中。

令U为第一步算子的组合，构造振幅放大算子


Gi=USiU-1Z(5.2.10)

式中：  Si只改变初始态|0〉|0〉m|0〉m的符号； Z作用于第三寄存器用于改变式(5.2.9)中|1〉的符号。

执行量子振幅估计，将存储在振幅中的θi转移到第二寄存器的基态中，即


|ψ4〉=|0〉l12e-iπθi|2mθi〉|δi+〉+eiπθi|2m(1-θi)〉|δi-〉|i〉
=|0〉l|δi〉|i〉(5.2.11)

式中：  |δi〉=12e-iπθi|2mθi〉|δi+〉+eiπθi|2m(1-θi)〉|δi-〉，包含第二寄存器、第三寄存器、第四寄存器和第五寄存器，-e±2iθi为Gi的特征值，|δi±〉为对应的特征向量。

三角函数等一些基本的函数可以用量子线路来实现（见附录B），因此总可以实现一个算子QA，能使存储在第二寄存器中的函数Fi=1-2sin2(πθi)存储在第一寄存器中，第一寄存器存储的量子态为|Fi〉=|1-2sin2(πθi)〉。因此经过算子QA之后式(5.2.11)演化为


|ψ5〉=|Fi〉|δi〉|i〉(5.2.12)


对第二寄存器、第三寄存器、第四寄存器和第五寄存器实施退计算，可得


|ψ6〉=|Fi〉|i〉(5.2.13)


至此，保真度被存储于基态中。也就是说，如果记上述量子线路为εi，经过εi之后，第一寄存器和第六寄存器的量子态由|0〉l|i〉演化为|Fi〉|i〉，第二寄存器至第五寄存器为辅助寄存器，输入和输出全为|0〉。因此，在后续的描述的中记εi的输出为|Fi〉|i〉。图5.6中，εi的输入和输出只画出了第一寄存器和第六寄存器，其余辅助寄存器没有再体现，可以理解为εi内部的寄存器。

2. 寻找和待分类样本最近邻的K个样本

下面介绍如何得到距离最近的K个样本，也就是得到K个最大的保真度。要找K个最大值，需要先随机选取K个下标，记为A={i0,i1,…,iK-1}，对于A中的每个元素都执行最大值搜索算法中的第二步。使用黑箱算子Oi′,A，使其能够满足


Oi′,A|0〉|i〉=|fi′,A(i)〉|i〉(5.2.14)

式中


fi′,A(i)=1,Fi>Fi′，iA
0,其他

式(5.2.14)表示，对于i′∈A，找到一个iA，使得当Fi>Fi′成立时，有fi′,A(i)=1。

下面给出黑箱Oi′,A的实现方法，量子线路图如图5.7所示。



图5.7Oi′,A的量子线路图


初始输入为第四寄存器至第七寄存器的|ζ0〉=|0〉|i′〉|0〉|i〉，利用εi和εi′可以将其演化为


|ζ1〉=|Fi′〉|i′〉|Fi〉|i〉(5.2.15)


使用比较门(J)比较第四寄存器和第六寄存器，并将结果存储在第三寄存器中，式(5.2.15)演化为


|ζ2〉=|g(i)〉|Fi′〉|i′〉|Fi〉|i〉(5.2.16)

式中


g(i)=1，Fi>Fi′
0，Fi≤Fi′


增加一个辅助量子比特用来判断下标i是否属于集合A，这里使用不等门(D)来实现。若D(il)用于标记下标il是否属于A，则D=D(i0)…D(iK-1)。将D作用于式(5.2.16)中的第七寄存器并将结果存储于第二寄存器时，可得


|ζ3〉=|χA(i)〉|g(i)〉|Fi′〉|i′〉|Fi〉|i〉(5.2.17)

式中


χA(i)=1,i∈A
0,iA

也就是说，D(i0)…D(iK-1)标记了已经属于A的K个下标，以避免前K个保真度有重复。

最终要构建一个黑箱使得g(i)=1且χA(i)=0，因此使用一个X门作用于第二寄存器，再使用Toffoli门作用于第一寄存器至第三寄存器，可得


|ζ4〉=|fi′,A(i)〉|χA(i)〉|g(i)〉|Fi′〉|i′〉|Fi〉|i〉(5.2.18)

此时，如果fi′,A(i)=1，则满足条件； 否则，不满足条件。

对第二寄存器至第六寄存器执行退计算可得


|ζ5〉=|fi′,A(i)〉|i〉(5.2.19)


令Oi′,A表示上述所有操作的集合，则


Oi′,A|0〉|i〉=|fi′,A(i)〉|i〉(5.2.20)

5.2.5实现

假设|x1〉=32|0〉+12|1〉和|x2〉=12|0〉-12|1〉分别是属于类别1和类别2的数据，本实验旨在计算一个待分类数据|x〉=12|0〉+12|1〉与|x1〉和|x2〉的距离，并比较出待分类数据与哪个类别的数据更接近，也就是与哪个类别的保真度更大。

考虑到量子线路的复杂性，本实验分成两部分：  第一部分将保真度信息存储在振幅中，并通过测量得到该振幅； 第二部分将上述振幅存储到基态中，并比较大小，进而得到待分类数据距离哪个类别更近。

下面先介绍第一部分实验，量子线路图如图5.8所示。

第一步：  使用交换测试将保真度信息存储到振幅中。

用两个不同的W门分别在q7和q15上制备训练数据|x1〉=32|0〉+12|1〉和|x2〉=12|0〉-12|1〉，用U门分别在q6和q14制备一个待分类数据|x〉=12|0〉+12|1〉，并执行一次交换测试得到|x〉与|x1〉的保真度F1=2sin2(πθ1)-1=cos(2πθ1)，以及|x〉与|x2〉的保真度F2=2sin2(πθ2)-1=cos(2πθ2)。

第二步：  添加辅助量子比特q1q2q3q4和q9q10q11q12，执行量子振幅估计算法，将和保真度相关的24θ1和24θ2存储在基态q1q2q3q4和q9q10q11q12上。

第三步：  添加辅助量子比特q0和q8，使用受控Ry8π8、Ry4π8、Ry2π8、Ryπ8将保真度F1和F2存储到量子比特q0和q8上。

最后分别对q0和q8进行测量，得到|0〉的概率，再开根号即为保真度。测量结果如图5.9所示。由图5.9(a)可以看出，对q0测量得到0的概率为0.854，因此保真度F1=0.854=0.9236。由图5.9(b)可以看出，对q8测量得到0的概率为0，因此保真度F2=0=0。






图5.8计算保真度的量子线路图




图5.9量子比特q0和q8的测量结果


第二部分实验完成了分类，其量子线路图如图5.10所示。





图5.10分类量子线路图


在第一部分的实验中，将保真度信息存储到q0和q8的振幅中，为了比较保真度的大小，利用量子振幅估计将存储在振幅中的保真度F=2sin2(πθ)-1=cos(2πθ)转移到辅助量子比特q6q7q8和q11q12q13中，再利用量子比较器比较两个保真度的大小。

第一步：  在q10和q15上制备与第一部分中q0和q8相同的振幅。

第二步：  执行量子振幅估计将振幅存储到q6q7q8和q11q12q13上。

第三步：  使用比较门比较q6q7q8和q11q12q13的大小关系。两组的三个量子比特代表的十进制数分别为y1和y2，则保真度分别为F1=121-cosπy12n-1和F2=121-cosπy22n-1。如果0≤πy2n-1≤π，其中y∈{y1,y2}，则可以根据y1和y2判断F1和F2的大小，即当y1>y2时，有F1>F2。由图5.11可以看出，q0q1=|10〉，即y1>y2，因此F1>F2。也就是将|x〉划分到样本|x1〉所在的类中。



图5.11分类测量结果


量子K近邻算法的两部分的代码如下所示：  

第一部分代码：  


1.%matplotlib inline

2.from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

3.from qiskit import execute

4.from qiskit import BasicAer

5.from qiskit import IBMQ

6.from qiskit import Aer

7.from math import pi

8.from qiskit.tools.visualization import plot_histogram

9.

10.circuit = QuantumCircuit(16,16)

11.

12.#定义W门： 制备训练集

13.def W_gate(n):

14.circuit = QuantumCircuit(1)

15.circuit.ry(n,0)

16.circuit= circuit.to_gate()

17.circuit.name = "W"








18.return circuit

19.

20.#定义U门： 先制备测试数据，再对训练数据和测试数据做swap-test得到两者的保真度

21.def U_gate():

22.circuit = QuantumCircuit(3)

23.circuit.h(2)

24.circuit.h(0)

25.circuit.cswap(0,1,2)

26.circuit.h(0)

27.circuit= circuit.to_gate()

28.circuit.name = "U"

29.return circuit

30.

31.#定义G门中的子门

32.def xcz():

33.circuit = QuantumCircuit(2)

34.circuit.x(0)

35.circuit.x(1)

36.circuit.cz(1,0)

37.circuit.x(1)

38.circuit.x(0)

39.circuit= circuit.to_gate()

40.c_U = circuit.control()

41.return c_U

42.

43.#定义G门： 量子相位估计

44.def G_gate(n):

45.circuit = QuantumCircuit(3)

46.circuit.z(0)

47.circuit.append(U_gate().inverse(),［i for i in range(3)］)

48.circuit.append(W_gate(n).inverse(),［i+2 for i in range(1)］)

49.circuit.x(2)

50.circuit.append(xcz(),［2］+［i for i in range(2)］)

51.circuit.x(2)

52.circuit.append(W_gate(n),［i+2 for i in range(1)］)

53.circuit.append(U_gate(),［i for i in range(3)］)

54.circuit= circuit.to_gate()

55.circuit.name = "G"

56.c_U = circuit.control()

57.return c_U

58.

59.#定义量子傅里叶逆变换

60.def qft_dagger(n):

61.qc = QuantumCircuit(n)

62.for qubit in range(n//2):

63.qc.swap(qubit, n-qubit-1)

64.for j in range(n):

65.for m in range(j):

66.qc.cp(-pi/float(2**(j-m)), m, j)

67.qc.h(j)

68.qc.name = "QFT+"








69.return qc

70.

71.#第一步

72.circuit.append(W_gate(pi/3),［i+7 for i in range(1)］)

73.circuit.append(U_gate(),［i+5 for i in range(3)］)

74.circuit.barrier(0,1,2,3,4,5,6,7)

75.

76.#第二步

77.for i in range(4):

78.circuit.h(i+1)

79.for i in range(4):

80.for j in range(2**i):

81.circuit.append(G_gate(pi/3),［i+1］+［m+5 for m in range(3)］)

82.circuit.append(qft_dagger(4),［i+1 for i in range(4)］)

83.

84.#第三步： 计算保真度到辅助量子比特

85.circuit.cry(8*pi/4,4,0)

86.circuit.cry(4*pi/4,3,0)

87.circuit.cry(2*pi/4,2,0)

88.circuit.cry(pi/4,1,0)

89.

90.#测量

91.circuit.measure(0,0)

92.

93.#在线路的下半部分重复上述操作

94.circuit.append(W_gate(-pi/2),［i+15 for i in range(1)］)

95.circuit.append(U_gate(),［i+13 for i in range(3)］)

96.circuit.barrier(8,9,10,11,12,13,14,15)

97.for i in range(4):

98.circuit.h(i+9)

99.for i in range(4):

100.for j in range(2**i):

101.circuit.append(G_gate(-pi/2),［i+9］+［m+13 for m in range(3)］)

102.circuit.append(qft_dagger(4),［i+9 for i in range(4)］)

103.circuit.cry(8*pi/4,12,8)

104.circuit.cry(4*pi/4,11,8)

105.circuit.cry(2*pi/4,10,8)

106.circuit.cry(pi/4,9,8)

107.circuit.measure(8,8)

108.

109.#绘制线路图

110.circuit.draw(output='mpl', plot_barriers=False, fold=-1)

111.backend = Aer.get_backend('qasm_simulator')

112.job_sim = execute(circuit, backend, shots=8192)

113.sim_result = job_sim.result()

114.

115.#绘制结果图

116.measurement_result = sim_result.get_counts(circuit)

117.print(measurement_result)

118.plot_histogram(measurement_result)





第二部分代码：  


1.%matplotlib inline

2.from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

3.from qiskit import execute

4.from qiskit import Aer

5.from math import pi

6.from qiskit.tools.visualization import plot_histogram

7.from comp import comp

8.

9.circuit = QuantumCircuit(16,16)

10.

11.#定义Us门

12.def Us():

13.circuit=QuantumCircuit(2)

14.circuit.h(0)

15.circuit.cry(7*pi/4,0,1)

16.circuit.x(0)

17.circuit.cry(-7*pi/4,0,1)

18.circuit.x(0)

19.circuit.h(0)

20.circuit= circuit.to_gate()

21.circuit.name = "Us"

22.return circuit

23.

24.#定义Us1门

25.def Us1():

26.circuit=QuantumCircuit(2)

27.circuit.h(0)

28.circuit.cry(pi,0,1)

29.circuit.x(0)

30.circuit.cry(-pi,0,1)

31.circuit.x(0)

32.circuit.h(0)

33.circuit= circuit.to_gate()

34.circuit.name = "Us1"

35.return circuit

36.

37.#定义UG门

38.def UG():

39.circuit=QuantumCircuit(2)

40.circuit.z(0)

41.circuit.append(Us().inverse(),［i for i in range(2)］)

42.circuit.x(1)

43.circuit.x(0)

44.circuit.cz(0,1)

45.circuit.x(0)

46.circuit.x(1)

47.circuit.append(Us(),［i for i in range(2)］)

48.circuit= circuit.to_gate()

49.circuit.name = "UG"








50.c_U = circuit.control()

51.return c_U

52.

53.#定义UG1门

54.def UG1():

55.circuit=QuantumCircuit(2)

56.circuit.z(0)

57.circuit.append(Us1().inverse(),［i for i in range(2)］)

58.circuit.x(1)

59.circuit.x(0)

60.circuit.cz(0,1)

61.circuit.x(0)

62.circuit.x(1)

63.circuit.append(Us1(),［i for i in range(2)］)

64.circuit= circuit.to_gate()

65.circuit.name = "UG1"

66.c_U = circuit.control()

67.return c_U

68.

69.#定义量子傅里叶逆变换

70.def qft_dagger(n):

71.qc = QuantumCircuit(n)

72.for qubit in range(n//2):

73.qc.swap(qubit, n-qubit-1)

74.for j in range(n):

75.for m in range(j):

76.qc.cp(-pi/float(2**(j-m)), m, j)

77.qc.h(j)

78.qc.name = "QFT+"

79.return qc

80.

81.#第一步

82.circuit.append(Us(),［i+9 for i in range(2)］)

83.circuit.barrier(6,7,8,9,10)

84.circuit.append(Us1(),［i+14 for i in range(2)］)

85.circuit.barrier(11,12,13,14,15)

86.

87.#第二步

88.for i in range(3):

89.circuit.h(i+6)

90.for i in range(3):

91.for j in range(2**i):

92.circuit.append(UG(),［i+6］+［m+9 for m in range(2)］)

93.circuit.append(qft_dagger(3),［i+6 for i in range(3)］)

94.#在线路的下半部分重复上述操作

95.for i in range(3):

96.circuit.h(i+11)

97.for i in range(3):

98.for j in range(2**i):

99.circuit.append(UG1(),［i+11］+［m+14 for m in range(2)］)

100.circuit.append(qft_dagger(3),［i+11 for i in range(3)］)








101.

102.#第三步

103.circuit.append(comp(),［i for i in range(16)］)

104.

105.#测量

106.circuit.measure(0,0)

107.circuit.measure(1,1)

108.

109.#绘制线路图

110.circuit.draw(output='mpl', plot_barriers=False, fold=-1)

111.backend = Aer.get_backend('qasm_simulator')

112.job_sim = execute(circuit, backend, shots=8192)

113.sim_result = job_sim.result()

114.

115.#绘制结果图

116.measurement_result = sim_result.get_counts(circuit)

117.plot_histogram(measurement_result)





5.3量子决策树

决策树(Decision Tree，DT)是一种具有树形结构的机器学习方法。在学习过程中，由样本集形成一棵可分层判决的树。例如，通过天气情况判断是否去打网球，有天气、湿度和风力三个特征，其中天气包括晴、阴和雨，湿度包括高和正常，风力包括强和弱。图5.12(a)是在各种天气特征下是否打网球的样本。决策树就是要根据已经给出的带标签的样本训练一棵树，当给出一个新的样本时，通过这棵树做出决策。图5.12(b)是根据打网球样本给出的决策树示例。本节首先介绍决策树的基本原理，然后介绍决策树的量子版本——量子决策树。



图5.12样本集及其对应的决策树示例


5.3.1决策树基本原理

假设N个训练样本组成的数据集为


X={(xi,yi):xi∈RM,yi∈{0,1,…,K-1}}i=0,1,…,N-1(5.3.1)

式中：  xi为单个样本的M维特征向量，xi=(x0ix1i…x(M-1)i)T(i=0,1,…,N-1)； yi表示第i个样本的类别，共有K≥2个取值，表示数据集共有K类。

一棵决策树由若干节点和分支组成，最顶端的节点称为根节点，所有节点都是从根节点开始。节点对应数据中的某一个特征，该特征有几个取值就从这个节点向下引出几个分支，也就是根据这个特征将数据分为若干类别。每个叶节点代表一种分类结果，除根节点和叶节点之外的节点称为内部节点。

由于样本包含多个特征，将哪一个特征作为根节点以及选择哪个特征作为下一个节点是决策树算法的核心。目前常用的算法包括ID3算法、ID4.5算法以及CART算法。下面给出最简单的ID3算法，为此首先给出熵和条件熵的定义。

对于式(5.3.1)中的数据集来说，假设一个样本属于类别k(k=0,1,…,K-1)的概率为pk，则数据集的熵定义为


H(X)=-∑K-1k=0pklogpk(5.3.2)

式中：  pk通常取值为ckN，ck为第k类样本的数目。

则计算熵的公式为


H(X)=-∑K-1k=0ckNlogckN(5.3.3)

熵表示对样本进行分类时的平均不确定性。

进一步，下面给出条件熵的定义。假设一个特征表示为A，该特征将数据集X划分为I个子集，分别为X0,X1,…,XI-1，各子集的样本数量分别为Ni(i=0,1,…,I-1)，cik为子集Xi中标注为第k类的样本数量。则cikNi表示子集Xi中一个样本属于类别k的概率，NiN表示X中一个样本属于子集Xi的概率，特征A的条件熵定义为


H(X|A)=-∑I-1i=0∑K-1k=0NiNcikNilogcikNi=-∑I-1i=0∑K-1k=0cikNlogcikNi(5.3.4)

式中：  cikNi为在知道一个样本属于子集Xi的条件下属于类别k的条件概率； cikN为一个样本既属于子集Xi又属于类别k的联合概率。

特征A的条件熵表示根据特征A，在已经知道一个样本属于某个子集Xi的条件下，对数据进行分类时的平均不确定性。

特征A的熵增益定义如下：  


G(X,A)=H(X)-H(X|A)(5.3.5)

表示在知道特征A的前后，样本分类的不确定的差值，也就是特征A带来的信息量。

ID3决策树算法选择熵增益最大的特征作为根节点，也就是一次分类能带来最大信息量的特征。具体算法：  首先计算所有特征的熵增益，熵增益最大的特征作为根节点； 然后根据该特征的取值向下引出分支； 再计算除根节点之外内部节点其他特征的熵增益，再选择熵增益最大的特征。依次进行下去，当子集Xi的熵为H(Xi)=0时，该节点为叶节点，输出其对应的标签类型。H(Xi)=0意味着Xi中只有一个类。

5.3.2量子决策树算法

与经典决策树算法类似，量子决策树算法也要找到能判别哪些节点可以作为根节点和内部节点的判别准则。下面首先给出该算法中样本的表示方法，然后介绍节点划分标准，最后给出量子决策树。

1. 样本表示方法

与之前的算法有所不同，该算法将每个样本中的特征都以叠加态的形式存储，但是并没有将所有样本以叠加态的形式存储在量子态中，数据集的量子表示为


X={(|x0〉,|y0〉),(|x1〉,|y1〉),…,(|xN-1〉,|yN-1〉)}(5.3.6)


由于数据集X共分成K类，则用Y={|Y0〉,|Y1〉,…,|YK-1〉}表示类别集，其中Yk=k(k=0,1,…,K-1)表示类别标签，即Y={|0〉,|1〉,…,|K-1〉}。

2. 节点划分标准

在经典算法中选择根节点和内部节点是决策树的重要内容，在量子算法中也是如此。和经典熵定义不同，量子算法使用量子熵。下面介绍量子熵的定义。

对于节点t来说，假设属于节点t的样本分属Nt个类别，则分类集记作Y(t)={|Y(t)0〉,|Y(t)1〉,…,|Y(t)Nt-1〉}。则量子熵定义为


S(ρ(t))=-tr(ρ(t)logρ(t))(5.3.7)

式中：  ρ(t)为Y(t)的密度算子，ρ(t)=∑Nt-1i=0p(t)i|Y(t)i〉〈Y(t)i|，p(t)i表示Y(t)中属于类别Y(t)i的样本的比例。

假设根据特征A，Y(t)可分成J个子节点，即


Y(t)={Y(t0),Y(t1),…,Y(tJ-1)}(5.3.8)

式中：  Y(tn)=|Y(tn)0〉,|Y(tn)1〉,…,|Y(tn)Ntn-1〉(tn=t0,t1,…,tJ-1)，Ntn表示属于子节点tn的样本共有Ntn类。

则量子期望熵可定义为


Se(ρ(t))=∑J-1n=0p(t)tnS(ρ(tn))(5.3.9)

式中：  ρ(tn)为Y(tn)的密度算子； p(t)tn为Y(t)中属于Y(tn)的样本的比例。

量子熵表示将Y(t)存储在量子态中所需要的最少量子比特数量，量子熵越小，需要的量子比特数量越少。对于节点t来说，根据不同的特征划分时会有不同的量子期望熵，该量子期望熵相当于经典算法中的条件熵，期望熵越小越好。也就是说，选择量子期望熵最小的特征作为下一个子节点。

3. 量子决策树

量子决策树首先选择期望熵最小的特征作为根节点，然后计算根节点中每个特征的量子期望熵，选择量子期望熵最小的特征作为下一层的根节点。之后，对每个内部节点重复以上选择新特征的过程，一直持续到满足以下两个停止标准中的任何一个为止：  

(1)  每个特征都已经包含在树中； 

(2)  与当前节点相关的特征都有相同的目标，即它们的量子熵为零。

最终完成量子决策树的构建。

5.4本章小结

本章讨论了三种量子分类方法，分别为量子支持向量机、量子K近邻和量子决策树。

量子支持向量机是一种二分类机器学习算法。本章主要介绍了线性最小二乘支持向量机的量子形式，并简单介绍了核函数。基于此算法，目前已经产生了大量的量子支持向量机算法，包括QSVM多分类算法和基于标准支持向量机的量子算法等，感兴趣的读者可参见文献［812］。

K近邻算法不需要训练就能预测分类。而量子K近邻算法利用量子叠加、并行特性能够更快地完成任务。此算法主要使用了两种量子技术：  交换测试用于计算样本间的保真度； 量子最大值搜索算法用于找到最近邻的K个值。

相较于前两种算法，量子决策树算法是一种计算复杂度不高、对中间值的缺失不敏感的分类方法。


参考文献