聚类是将一组物理抽象对象分类为由相似对象组成的不同类别的过程.聚类产生的集群是一组数据对象，同一集群中的对象相似程度高.因此，聚类研究的是样本在尺度空间上的分布.在聚类问题[1-2]上，聚类样本数据中的离群点容易影响簇中心的选择，进而影响聚类结果，且样本点规模的扩大会造成算法需要在样本点间的距离计算上消耗大量计算资源，这些都导致算法在复杂度和精度上存在一些不足.为了研究量子计算在聚类问题上的应用与扩展，Horn等人[3]提出量子聚类(quantum clustering, QC)算法.不同于经典的K-Means[4]和K-Medians[5]算法，QC算法在迭代过程中用于聚类的度量距离相对固定，学习速率不容易确定.2007年，李志华等人[6-8]对QC算法进行了改进，提出了基于距离的量子聚类算法，该算法解决了QC算法在迭代过程中的缺陷.此外，Zhang等人[9]通过指数距离函数对QC算法中样本点间距离计算方法和迭代过程作出改进，提出了新型量子聚类算法,EDQC算法.但上述算法的簇中心的选取很容易受到离群点以及聚类规模的影响，当待聚类的样本点线性不可分时，这些算法聚类效果并不是很好.

针对聚类问题，本文提出了一种新型的量子主成分分析算法——QPCA算法(quantum principal component analysis algorithm)，结合奇异值分解[10]的思想，用于提取待聚类数据的主成分，以便选取更为准确的簇中心.此外，本文采用了Liu等人[11]提出的量子最小值搜索算法，通过优化不同样本点之间距离最小值搜索过程，降低聚类的迭代次数.实验部分采用Cirq[12]量子编程框架进行量子仿真验证，由于可使用的量子比特位数的限制，本文完成了小规模数据集情况下的量子实验的验证.

本文工作的主要贡献有3个方面:

1) 提出采用新型量子主成分分析算法，选取更为准确的簇中心，减少异常值对簇中心选择的影响;

2) 利用指数距离公式计算样本点到簇中心的距离，同时采用量子最小值搜索算法加快最短距离搜索，减少聚类所需迭代次数；

3) 采用Cirq量子编程框架完成相关量子仿真实验，比已有的传统及量子聚类算法、QC-PCA算法在聚类准确度和性能上都有不同程度的改进.

1 相关工作

本节中主要介绍主成分分析算法以及量子主成分分析算法的基本定义以及作用特点.

主成分分析(principal component analysis, PCA)算法[13-14]常用于数据分析，能够在保持数据集主要信息的同时降低数据集的维数(特征的数量).

量子主成分分析(QPCA)[15-18]是一种将量子计算与传统机器学习结合的量子降维算法，能够获取数据矩阵中最具有代表性的特征值对应的特征向量并进行重构. 具体的算法过程为：

假设存在具有n个样本点且每个样本点具有m维特征的数据集用矩阵X=(xn)来表示，每个样本点可以被表示为xi=(xij)，1≤i≤n，1≤j≤m，σ代表奇异值.

初始态制备阶段应用2个酉操作：

UM:|i〉|0〉

(1)

UN:|0〉|j〉

(2)

其中

酉操作UM和UN分别用于编码并得到初始样本点的量子态形式以及在幅度上编码样本点范数.X*为X的伴随矩阵.利用式(1)、式(2)这2个酉操作能够帮助操纵量子比特，得到需要的初始态：

|ψs〉=UMUN|0〉|0〉=

(3)

通过得到前D个样本点数据主成分的量子态形式，提取样本点数据的主成分.样本点的特征值可以被写为

(4)

σj表示奇异值.而量子态能够被表示为

(5)

其中|uj〉和|vj〉分别保存着矩阵的左奇异向量和右奇异向量.通过额外增加辅助量子位，求解密度矩阵的幂，并且对幺正运算W执行相位估计：

W=(2MM†-IND)(2NN†-IND)=

UM(IN⊗2|0〉〈0|-IND)UN(2|0〉

〈0|⊗ID-IND),

(6)

得到

(7)

增加一个索引寄存器，存储lb(d+1)个|0〉量子态的量子比特.通过执行受控酉操作CU(λ1),CU(λ2),…,CU(λd)，CU(λj):|λj〉|0〉|λj〉|j〉，能够得到量子态：

(8)

执行逆相位估计，将特征值寄存器释放，执行受控旋转操作CR(β1),CR(β2),…,CR(βd)，得到:

CR(βj):|j〉|0〉

(9)

其中，得到量子态：

(10)

经过投影测量最终可以得到:

(11)

经过上述步骤，存储所有数据点信息的量子态|ψs〉被转换成低维的量子态|ψe〉：

|ψs〉|ψe〉

(12)

其中，与经典PCA算法相比，QPCA算法的总时间复杂度有了指数级提高[18].

2 针对聚类问题的量子主成分分析算法

针对聚类问题，本文提出了QC-PCA算法.先将待聚类的原始数据集矩阵进行奇异值分解，利用预设的阈值更新奇异值并得到主成分，对原始数据集特征进行筛选和提取，再利用薛定谔方程表示筛选后的数据特征，分别采用波函数和势函数描述数据分布状态和势能大小，从而减少异常值对簇中心选取的影响，选取具有代表性的簇中心.此外，采用量子最小值搜索算法[11]寻找距离样本点最近的簇中心，减少聚类所需迭代次数.重复上述步骤，遍历所有样本点并完成聚类.本文提出的算法过程可以用算法1来描述.

算法1. QC-PCA算法.

输入：N个数据、维度M、k个聚类、阈值τ；

输出：样本聚类结果.

① 准备量子态：|ψ1〉=|0〉|0〉L|0〉C|ψs〉B；

② 附加量子位，执行酉操作W的相位估计,得到量子态：

③ 更新奇异值提取主成分,得到量子态集合：

④ 选取k个簇中心ci，i∈[1,k]；

⑤ for i=1,2,…,N-k do

⑥ 计算

⑦ 搜索样本点到簇中心的最小距离，聚类；

⑧ end for

⑨ 计算各类的质心作为新的簇中心；

⑩ 重复迭代⑤～⑨直至前后簇中心相同，完成聚类.

假设存在具有n个样本点且每个样本点具有m维特征的数据集用矩阵X=(xn)来表示，每个样本点可以被表示为xi=(xij)，1≤i≤n，1≤j≤m，σ代表奇异值，δ，k，τ分别表示测量距离，聚类类别以及预设的阈值.QC-PCA算法能够通过6个步骤来进行描述：

步骤1. 量子态准备.

利用UM,UN这2个酉操作分别编码并得到初始样本点的量子态形式以及在幅度上编码样本点范数，产生想要的初态.制备处于|0〉量子态的量子比特，通过式(3)得到最终的量子态为|ψ1〉=|0〉|0〉L|0〉C|ψs〉B.

步骤2. 奇异值分解.

步骤1得到的初态能够采用主成分分析的思想进行奇异值分解，得到前d个表示数据主要特征的量子态形式的主成分|v1〉,|v2〉,…,|vd〉，它们相应的所占方差比例可以用式(4)表示.根据式(1)(2)(4)，式(3)可以被化简为

(13)

通过额外增加辅助量子位，求解密度矩阵的幂，并且在第2个寄存器上利用式(6)对幺正运算W执行相位估计，得到量子态：

(14)

步骤3. 更新奇异值提取主成分.

定义yj=(σj-τ)/σj=1-τ/σj，其中yj∈[0,1),利用受控旋转操作，并且附加一个索引寄存器，该寄存器存储着lb(d+1)个|0〉量子态的量子比特.执行D个受控酉操作CU(y1),CU(y2),…,CU(yD)，利用加减阈值更新奇异值大小.通过附加1个用于记录大于阈值的奇异值的下标的量子位，得到量子态：

(15)

其中筛选出的主成分可以被表示成定义由于当前筛选出的主成分数据是奇异值与阈值相减后的差值，而聚类问题的簇中心数据需要使用原始数据，所以还需要执行1次受控旋转操作，并取反对应的旋转角度.若执行d个受控酉操作是利用阈值还原后的奇异值，得到量子态：

(16)

利用2种受控旋转操作消除了阈值变化，实现了高保真、高概率的矩阵逼近.量子主成分分析算法的整个电路设计如图1所示：

步骤4. 选取簇中心.

筛选后的数据集样本点可以被描述为量子力学中的希尔伯特空间中的粒子，其分布能够用薛定谔方程表示为

(17)

其中H,V,E分别表示哈密顿算符，势函数以及H可能的特征值.利用势函数V可以写出特征态函数，也就是高斯波函数表示：

(18)

除此之外，在给定波函数Ψ时，利用Schrödinger方程也可以求解出决定样本点分布的势函数V，即

i∈{1,2,…,k}.

(19)

簇中心ci可以用从势能值集合中挑选出的k个最小值数据xi来表示.

步骤5. 计算样本点到各簇中心距离.

随机挑选出一个样本点数据，利用指数距离公式

(20)

其中计算出样本点到k个聚类中心的距离.将其应用到剩余的所有样本点，得到量子态：

(21)

步骤6. 聚类.

计算样本点到各个簇中心点的距离，并采用量子最小值搜索算法[11]找到最小距离，完成该样本点的聚类.重复步骤5的过程，直到所有的数据样本被聚类为k个类别.然后计算同类别数据点的质心作为新的簇中心，假设第i个聚类中有f(X,Y)个点，则新的簇中心为

重复步骤5以及步骤6直至前后2个簇中心相同，聚类结束.

量子最小值搜索算法[11]随机选择一个数据d′,d′∈D，能够采用动态策略来增加目标状态，即拥有最小距离的量子态的概率幅.具体过程为：假设M表示每一轮次搜索最小值结束后输出的方案数量，如果数据集中的最小值是最后一轮搜索得到的，那么M=1.动态策略可被描述为：假设初始值t=1，t表示最大迭代次数，t的变化步长为当时，随机设置迭代次数t′，将t′次迭代的Grover-Long搜索[19]应用于|φ〉.当则在|φ〉上迭代tmax次Grover-Long搜索,如果测量值r小于上一轮保存的样本点间距离，将其替换并继续执行，迭代完成后返回最小数值.

3 实验仿真

3.1 实验设计

为了验证本算法的有效性和可行性，本文采用Cirq[12]量子编程框架实现小规模数据集下的量子算法验证.所有实验均运行在一台配置显存为40 GB的NVIDIA Tesla A100显卡，Intel GOLD 5220R CPU，256 GB内存的服务器上，编译语言采用Python，编译器采用Pycharm.

数据集包含120个待聚类的样本点，共3类，每个类别平均有40个待聚类样本点.采用sklearn框架，根据特征数量、中心点数量、范围等来生成特征值，设置随机数种子大小为100，减少人工生成数据或直接随机生成数据对于实验结果的影响.生成的数据经过标准化处理后再进行使用，防止数量级上的差异影响对聚类距离的判断，更准确地测试聚类算法的效果.部分生成的待聚类数据点的相关数据如表1所示：

S0～S119为随机生成的120个样本点，F0～F5表示每个样本点具有6个特征.待聚类数据点分布示意图如图2所示，相同颜色深度的点代表生成的相同类别的数据.

3.2 实验流程及对比分析

首先根据数据集，利用UM和UN酉操作准备量子态:

|ψ1〉=|0〉|0〉L|0〉C|ψs〉B,

(22)

其中|ψs〉满足式(3).接着将|ψ1〉进行奇异值分解，并附加量子位，执行酉操作W的相位估计，得到量子态：

(23)

计算yj=(σj-τ)/σj=1-τ/σj，yj∈[0,1)，执行受控旋转，根据旋转角度，利用受控旋转门将奇异值与阈值相减，筛选出d维大小的主成分，得到量子态：

(24)

计算还原主成分数据样本的奇异值，得到初始样本的子集，其量子态形式可以表示为

(25)

此时对应原数据，得到筛选后的数据点以及对应的聚类类别如表2所示：

从势函数集合中选择3个最小值作为簇中心ci，i∈{1,2,3}，实验得出S12、 S35样本、S93样本分别为该数据集聚类的3个初始簇中心.利用式(20)的指数距离公式对原始数据集进行距离计算，计算出每一个随机样本到这3个簇中心的距离.最后采用最小值搜索算法搜索出最小的距离，将此数据点分类到该类别中.直到所有样本数据点都计算完成，最终完成数据样本点的聚类分布.图4为最小值搜索算法的电路设计：

现有的量子聚类算法采用Grover算法搜索样本点到簇中心点距离的最小值.当数据规模较小时，Grover算法的成功率不能达到100%.本文在搜索过程中采用的最小值搜索算法[11]基于Grover-Long算法做出改进，提高搜索成功率，并且采用动态策略降低算法的复杂度，同时优化设计电路，缩减门的数量.

除此之外，本文在数据集统一的情况下，将提出的QC-PCA算法与QC算法、EDQC算法以及文献[20]提出的NSQC算法在聚类准确度(样本聚类正确的个数/总样本数)上进行比较，结果如图4所示.另外，图5展示的不同算法的聚类效果,图5(a)表示原始数据集样本点分布及所属类别，图5(b)～(e)分别表示QC，EDQC，NSQC以及提出的QC-PCA算法的聚类效果.从图4可以看出,经过10次迭代，4种算法的聚类准确度都趋于收敛，其中QC-PCA算法的聚类准确度最高，为0.78， NSQC算法的聚类准确度为0.75，EDQC算法的聚类准确度为0.74，QC算法的聚类准确度最低，为0.72.图5(e)代表的QC-PCA算法的聚类效果相对较好，相同类别的数据点的颜色相比较于其他聚类算法显得比较统一，图5(b)(c)(d)代表的QC，EDQC，NSQC算法的聚类结果相对较差，相同类别的数据点的颜色分布比较凌乱.

实验结果表明，本算法利用量子主成分分析算法对数据进行预处理，能够较为准确地选出具有更多主成分的数据点作为簇中心，降低了簇中心的选取对聚类精度的影响.另外，本算法采用优化后的量子最小值搜索算法，降低了样本点之间最短距离搜索的复杂程度.

4 性能评估

本节分别从簇中心选取和样本点之间最短距离搜索的时间复杂度以及资源消耗3个方面对提出的QC-PCA算法做出评估.假设存在N个M维的样本点数据，分为K类，迭代次数为T.

从簇中心选取时间复杂度来看，制备量子态的时间复杂度是O(log NM)，若假设表示最大特征值与最小特征值之比， 表示精确度，则幺正运算的时间复杂度为O(-1t2log NM).若将-1t2视为常数因子，与经典聚类算法中的K-Means算法相比，簇中心选取的总时间复杂度从O(TNM)降到了O(ploy(log NM))，有了指数级的提升.

从最短距离搜索时间复杂度来看，大部分经典搜索算法[21-22]的时间复杂度大于O(NM)，而本文采用优化的量子最小值搜索策略，搜索复杂度为

从资源消耗上来看，本文提出的QC-PCA算法与经典算法K-Means相比，从原来的O(NM)比特降到了O(log NM)量子比特，与其他量子算法相比，从O(N log M)量子比特降到了O(log NM)量子比特.表3选取K-Means算法、QC算法、EDQC算法、NSQC算法、QC-PCA算法，从簇中心选取时间复杂度，最短距离搜索时间复杂度和资源消耗这3个方面给出了具体的对比和评估.

根据表3可以直观看出，QC-PCA与传统算法和其他3个量子算法相比在簇中心选取时间复杂度、最短距离搜索时间复杂度以及资源消耗上均有不同程度的改进效果.

5 总 结

本文提出了一种针对聚类问题的量子主成分分析算法(QC-PCA算法)，利用奇异值分解的思想，减少异常值对簇中心选取的影响，并采用量子最小值搜索算法寻找距离样本点最近的簇中心，减少聚类所需迭代次数.仿真实验表明，QC-PCA算法与已有的量子聚类算法相比，提升了聚类准确度.性能评估表明，QC-PCA算法与已有的传统算法及量子聚类算法相比，在簇中心选取时间复杂度，最短距离搜索时间复杂度和资源消耗上均有不同程度的改进.

作者贡献声明：刘文杰是本研究的构思者，指导实验设计、数据分析、论文写作与修改；王博思是本研究的实验设计者和实验研究的执行人，完成数据分析，论文初稿的写作；陈君琇参与实验设计和实验结果分析.全体作者都阅读并同意最终的文本.

参考文献

[1]Hancer E, Xue Bing, Zhang Mengjie. A survey on feature selection approaches for clustering[J]. Artificial Intelligence Review, 2020, 53(6): 4519-4545

[2]Yuan Chunhui, Yang Haitao. Research on K-value selection method of K-means clustering algorithm[J]. Multidisciplinary Scientific Journal, 2019, 2(2): 226-235

[3]Horn D, Gottlieb A.The method of quantum clustering[C] //Proc of the 14th Int Conf on Neural Information Processing Systems: Natural and Synthetic. Cambridge,MA: MIT Press, 2001: 769-776

[4]Hartigan J A, Wong M A. A K-means clustering algorithm[J]. Journal of the Royal Statistical Society: Series C Applied Statistics, 1979, 28(1): 100-108

[5]Arora S, Raghavan P, Rao S. Approximation schemes for Euclidean k-medians and related problems[C] //Proc of the 30th Annual ACM Symp on Theory of Computing. New York: ACM, 1998: 106-113

[6]Li Zhihua, Wang Shitong. Improved algorithm of quantum clustering[J]. Computer Engineering, 2007, 33(23): 189-190 (in Chinese)(李志华, 王士同. 一种量子聚类的改进算法[J]. 计算机工程, 2007, 33(23): 189-190)

[7]Li Zhihua, Wang Shitong. Parameter-estimated quantum clustering algorithm[J]. Journal of Data Acquisition & Processing, 2008, 23(2): 211-214

[8]Li Zhihua, Wang Shitong. Fuzzy clustering algorithm for categorical data using quantum mechanics[J]. Journal of System Simulation, 2008, 20(8): 2119-2122

[9]Zhang Yao, Wang Peng, Chen Gaoyun, et al. Quantum clustering algorithm based on exponent measuring distance[C] //Proc of the 1st IEEE Int Symp on Knowledge Acquisition and Modeling Workshop. Piscataway, NJ: IEEE, 2008: 436-439

[10]Zhang Anru, Han Rungang. Optimal sparse singular value decomposition for high-dimensional high-order data[J]. Journal of the American Statistical Association, 2019, 114(528): 1708-1725

[11]Liu Wenjie, Wu Qingshan, Shen Jiahao, et al. An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12(11): 10425-10434

[12]Google. Cirq: A python library for NISQ circuits[CP/OL]. (2019-11-18)[2021-03-26]. http://cirq.readthedocs.io/en/stable

[13]Karamizadeh S, Abdullah S M, Manaf A A, et al. An overview of principal component analysis[J]. Journal of Signal and Information Processing, 2013, 4(3B): 173-175

[14]Bro R, Smilde A K. Principal component analysis[J]. Analytical Methods, 2014, 6(9): 2812-2831

[15]Lloyd S, Mohseni M, Rebentrost P. Quantum principal component analysis[J]. Nature Physics, 2014, 10(9): 631-633

[16]Lin Jie, Bao Wansu, Zhang Shuo, et al. An improved quantum principal component analysis algorithm based on the quantum singular threshold method[J]. Physics Letters A, 2019, 383(24): 2862-2868

[17]Xin Tao, Che Liangyu, Xi Cheng, et al. Experimental quantum principal component analysis via parametrized quantum circuits[J]. Physical Review Letters, 2021, 126(11): 110502

[18]Yu Chaohua, Gao Fei, Lin Song, et al. Quantum data compression by principal component analysis[J]. Quantum Information Processing, 2019, 18(8): 1-20

[19]Long Guilu. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64(2): 022307

[20]Casaa-Eslava R V, Jarman I H, Lisboa P J G, et al. Quantum clustering in non-spherical data distributions: Finding a suitable number of clusters[J]. Neurocomputing, 2017, 268: 127-141

[21]Mahboob T, Akhtar F, Asif M, et al. Survey and analysis of searching algorithms[J]. International Journal of Computer Science Issues, 2015, 12(3): 169-175

[22]Pan Yiwei, Pan Zhibin, Wang Yikun, et al. A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy[J]. Knowledge-Based Systems, 2020, 189: 105088

A Quantum Principal Component Analysis Algorithm for Clustering Problems

Liu Wenjie1,2, Wang Bosi2, and Chen Junxiu2

1(Engineering Research Center of Digital Forensics Ministry of Education (Nanjing University of Information Science and Technology), Nanjing 210044)2(School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044)

Abstract The outliers in the clustering problem can easily affect the selection of cluster centers, and the expansion of the clustering scale will cause more computing resources to be consumed in the calculation of the distance between sample points. To address the above issues, a new quantum principal component analysis algorithm for clustering problems (QC-PCA) is proposed, improving the selection of the cluster center and the shortest distance search. In this paper, the principal components are marked by adding and subtracting thresholds to singular values and the cluster center is selected according to the potential function of the subset, thereby reduce the influence of abnormal points on the selection of the cluster center. In addition, a quantum minimum search algorithm is used to find the cluster center closest to the sample point, reducing the number of iterations required for clustering. Taking a small-scale data set as an example, the Cirq quantum programming framework is used to circuit design and simulation experiments. The experimental results show that compared with the existing quantum algorithms, the proposed QC-PCA algorithm improves the clustering accuracy. Performance analysis shows that compared with the existing classical and quantum algorithms, our algorithm has different degrees of improvement in the time complexity of the cluster center selection and the shortest distance search. And the resource consumption of the proposed QC-PCA algorithm is also lower than that of them.

Key words quantum machine learning; clustering problem; quantum principal component analysis; quantum minimum searching algorithm; singular value decomposition

中图法分类号 TP181; O413

DOI:10.7544/issn1000-1239.20210333

收稿日期：2021-04-01；修回日期：2022-02-11

基金项目：国家自然科学基金项目(62071240)；江苏省高校优势学科建设工程项目(PAPD)

This work was supported by the National Natural Science Foundation of China (62071240) and the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).

Liu Wenjie, born in 1979. PhD, associate professor. His main research interests include quantum machine learning, quantum secure multi-party computation, quantum cryptography communication.

刘文杰，1979年生.博士，副教授.主要研究方向为量子机器学习、量子安全多方计算、量子密码通信.

Wang Bosi, born in 1996. Master. His main research interests include deep learning, quantum machine learning.

王博思，1996年生.硕士.主要研究方向为深度学习、量子机器学习.

Chen Junxiu, born in 1995. Master. Her main research interests include quantum machine learning, quantum cryptography communication.

陈君琇，1995年生.硕士.主要研究方向为量子机器学习、量子密码通信.