量子典型相关分析算法_王庆乐.pdf

第 40 卷 第 1 期量 子 电 子 学 报Vol.40 No.12023 年 1 月CHINESE JOURNAL OF QUANTUM ELECTRONICSJan.2023DOI:10.3969/j.issn.1007-5461.2023.01.014量量量子子子典典典型型型相相相关关关分分分析析析算算算法法法王庆乐1,2,3,薛 雪1,李元诚1(1 华北电力大学控制与计算机工程学院,北京 102206;2 北京邮电大学网络与交换技术国家重点实验室,北京 100876;3 中国科学技术大学量子信息重点实验室,安徽 合肥 230026)摘要:典型相关分析是一种重要的数据处理方法,用于处理随机向量之间的相互依赖关系。然而,经典的典型相关分析算法的复杂度对数据维度是多项式依赖的,致使该类算法并不适用于分析在大数据时代下规模呈指数增长的数据。针对经典的典型相关分析算法的这种缺陷,提出了一种量子典型相关分析算法。该算法把典型相关分析所涉及的优化问题转化为适合用量子计算技术处理的代数问题,并采用量子主成分分析技术进行求解,从而降低了典型相关分析算法的复杂度。在特定的参数条件下,所提算法可实现在数据维度上的指数加速,符合当今实际数据处理对该算法的需求。关 键 词:量子算法;量子主成分分析;相关分析;指数加速中 图 分 类 号:O413文 献 标 识 码:A文章编号:1007-5461(2023)01-00120-07Quantum canonical correlation analysis algorithmWANG Qingle1,2,3,XUE Xue1,LI Yuancheng1(1 School of Control and Computer Engineering,North China Electric Power University,Beijing 102206,China;2 State key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China;3 CAS Key Laboratory of Quantum Information,University of Science and Technology of China,Hefei 230026,China)Abstract:Canonical correlation analysis is an important data processing method for dealing with theinterdependence of random vectors.However,the complexity of the classical canonical correlation anal-ysis algorithm is polynomial dependent on the data dimension,making this type of algorithm not suitablefor analyzing the data whose scale is growing exponentially in the era of big data.Aiming at the defectof classical canonical correlation analysis algorithm,a quantum canonical correlation analysis algorithmwas proposed.The algorithm transformes the optimization problems involved in canonical correlationanalysis into algebraic problems suitable for quantum computing technology,and uses quantum principalcomponent analysis technology to solve it,thereby reducing the cost of canonical correlation analysis基金项目:国家自然科学基金(61801126),北京邮电大学网络与交换技术国家重点实验室开放项目(SKLNST-2021-1-05),中国科学技术大学中国科学院量子信息重点实验室开放项目(KQI201902),信息网络安全公安部重点实验室开放课题(C21605),中央高校基本科研业务(2020MS014)作者简介:王庆乐(1987-),女,山东临沂人,博士,副教授,主要从事量子密码、量子信息论、量子计算方面的研究。E-mail:收稿日期:20210406;修改日期:20210513通信作者。E-mail:第 1 期王庆乐等:量子典型相关分析算法121algorithms.Under certain parameter conditions,the proposed algorithm can achieve exponential accel-eration in the data dimension,which meets the requirements of this algorithm for todays actual dataprocessing.Key words:quantum algorithm;quantum principal component analysis;correlation analysis;exponential acceleration0引言量子计算在处理某些特定问题时有比经典计算更强的计算能力,如质因数分解1、非结构化数据搜索2和矩阵计算问题35。近年来,随着量子计算机的发展,量子机器学习(QML)受到了广泛关注。QML 研究的一个重要方向是设计量子算法来加速机器学习,包括数据分类6,7和线性回归等810。严格来说,大部分机器学习算法实际上也是统计分析算法,统计分析中的一种重要方法为典型相关分析。实际上,当需要分析和研究两组变量之间的关系时,通常会用到典型相关分析。例如,为了研究财政政策实施以后对经济发展的影响,需要考察有关财政政策的一系列指标(如财政支出总额、财政赤字、国债发行额、税率等)与经济发展的一系列指标(如国内生产总值、就业率等两组变量)之间的相关程度。典型相关分析方法最初由 Hotelling11在 1936 年提出。2004 年,Hardoon 等12对该方法进行了综述,并提出了其在学习方法上的应用。2005 年,Sun 等13提出把典型相关分析用于特征融合。近年来,典型相关分析研究不断发展,其变体也相继被提出,包括基于核理论的典型相关分析14、基于流形结构的典型相关分析15、基于监督学习的典型相关分析16、稀疏典型相关分析等17,18。当数据量很大时,典型相关分析算法运算速度很慢,耗时严重,因此其不适用于大数据时代。本文利用量子计算的优势降低典型相关分析算法的复杂度,并提出了量子典型相关分析算法。所提出量子算法在特定参数条件下,相对经典典型相关分析在维度上有指数加速效果。1典型相关分析1.1典典典型型型相相相关关关分分分析析析的的的提提提出出出典型相关分析的目的是寻求两组变量中每一组变量的线性组合,使得两组变量的线性组合之间的相关性最大化。一般的相关性分析依赖于变量的坐标系,即使两组多维变量之间本质上存在非常强的线性关系,坐标系选取不恰当也会导致线性关系不可见12。典型相关分析通过研究两组综合指标之间的关系来研究变量之间的线性关系,可用于挖掘一般相关性分析中的不可见关系。具体地,考虑两组多变量随机向量:X=x0,x1,xn1 和 Y=y0,y1,ym1,其中 xi和 yj均为l 维向量。定义一个线性组合 wx,使得矩阵 X 列向量之间的一个线性组合为 zx=Xwx。同理,可定义zy=Ywy。典型相关分析通过选择合适的 wx和 wy,使投影后的向量具有最大的相关性,即最大化函数=maxwx,wycorr(zx,zy)=maxwx,wyzx,zyzxzy,(1)式中 ,表示向量的内积。此时,得到的 wx和 wy对被称为第一对典型变量,记为 w(0)x和 w(0)y,对应的 被称为第一个典型相关系数,记为 1。继而,由 w(0)x和 w(0)y出发,计算第二对典型向量,即寻找与 w(0)x和w(0)y分别正交且同时使投影后的向量具有最大相关性的向量 w(1)x和 w(1)y。依此类推,可得到 d 对典型向量,d 为问题需要抽取的典型向量数量。122量 子 电 子 学 报40 卷1.2典典典型型型相相相关关关分分分析析析的的的求求求解解解及及及其其其复复复杂杂杂度度度记 x,y 的协方差矩阵为 C(x,y),则C(x,y)=E|xy|xy|T|=|CxxCxyCyxCyy|=C,(2)式中:Cxx和 Cyy为集内协方差矩阵;Cxy和 Cyx为集间协方差矩阵;Cxy是 CTyx的转置,Cxy=CTyx。此时=maxwx,wywTxCxywywTxCxxwxwTyCyywy.(3)当 取得最大值时即为最大典型相关系数,此时|0CxyCyx0|wxwy|=|Cxx00Cyy|wxwy|.(4)综上所述,求解典型相关分析问题可以转化为求解一般特征值问题。不失一般性,假设该特征值问题的解为 1,1,2,2,p,p,0,其中 1 2 p 0。在这里,特征值 1,2,p就是典型相关系数,对应的特征向量|wxwy|即为典型向量对 wx和 wy。经典算法求解(4)式转化为求一般特征值问题,计算复杂度为 O(poly(nml),其中 n、m 分别是随机向量 X、Y 中的随机变量个数,l 是随机变量 xi和 yj的维度。2量子典型相关分析2.1问问问题题题转转转化化化显然|Cxx00Cyy|是半正定矩阵,假设|Cxx00Cyy|可逆,则以下定理成立:定理 1:求解典型相关分析问题,等价于求解一般特征值问题|Cxx00Cyy|1|CxxCxyCyxCyy|I|wxwy|=|wxwy|.(5)如果|Cxx00Cyy|不可逆,可取|Cxx00Cyy|的伪逆,定理 1 仍然成立。进而,可将问题转化为求一般特征值问题|Cxx00Cyy|1|CxxCxyCyxCyy|wxwy|=(+1)|wxwy|.(6)令 =|Cxx00Cyy|12|wxwy|,则(6)式转化为|Cxx00Cyy|12|CxxCxyCCyy|Cxx00Cyy|12=(+1),(7)第 1 期王庆乐等:量子典型相关分析算法123显然|Cxx00Cyy|12|CxxCxyCyxCyy|Cxx00Cyy|12是对称半正定矩阵,只需取最大的d个特征值0,1,d1及其对应的特征向量 1,d。因此,典型相关分析问题的 d 个典型相关系数分别为 0 1,11,d1 1,对应典型相关向量对为|w(i)xw(i)y|=|Cxx00Cyy|12i,i=0,1,d 1.(8)2.2量量量子子子典典典型型型相相相关关关分分分析析析算算算法法法设设设计计计量子算法的输入是矩阵 X=x0,x1,xn1 和 Y=y1,y2,ym。简单起见,令 n=m。实际上,如果 n m,可令 Y=y1,y2,ym,y1,y2,ynm。由于要找的是一个向量之间的线性组合,因此对 Y进行这样的处理不会影响最终结果。不妨假设向量 xi和 yj(i,j 0,1,n 1)均为归一化向量,即|xi22=jx2ij=1yj22=ky2jk=1.(9)假设输入存储在一个经典的数据结构中,那么量子访问数据结构可以高效创建矩阵 X 和 Y 的每一列对应的量子态|xi=jxij|j|yj=kyjk|k,(10)以及每一列的二范数组成的向量对应的量子态|?X和|?Y,创建这些量子态的复杂度均为Opolylog(mnl)。要求解(7)式,根据量子主成分分析和量子线性判别分析,首先需要构建一个量子态,其与矩阵|Cxx00Cyy|12|CxxCxyCyxCyy|Cxx00Cyy|12成比例,即|Cxx00Cyy|12|CxxCxyCyxCyy|Cxx00Cyy|12.(11)然后用 做量子主成分分析,得到最大的 d 个特征值对应的特征向量 1,d。最后,用量子求逆算法求解|wxiwyi|=|Cxx00Cyy|12i,i=1,2,d.(12)量子典型相关分析算法的步骤如下:步骤 1:制备量子态。首先,制备|CxxCxyCyxCyy|对应的量子态 和|Cxx00Cyy|对应的量子态。因为Cxx=1n 1XTX=1n 1nixi|xj|ij|,(13)124量 子 电 子 学 报40 卷所以有|CxxCxyCyxCyy|=1n 1nij|00|xi|xj|ij|+|01|xi|yj|ij|+|10|yi|xj|ij|+|11|yi|yj|ij|Cxx00Cyy|=1n 1nij|00|xi|xj|ij|+|11|yi|yj|ij|.(14)的制备过程为:1)初始化量子态|0logn|0|0logl。定义本文中对数以 2 为底,即 logn=log2n,logl=log2l;2)对前 log(n)+1 个量子比特分别做 Hadamard 操作,可得量子态1nni|i12(|0+|1)|0logl;3)受控访问数据结构 见(10)式,可得1nni|i12(|0|xi+|1|yi)。此时,对第三量子寄存器取偏迹,即得量子态=12nnij|00|xi|xj|ij|+|01|xi|yj|ij|+|10|yi|xj|ij|+|11|yi|yj|ij|.(15)的制备过程为:1)初始化量子态|0logn|0|0|0logl;2)对前 log(n)+1 个量子比特分别做 Hadamard 操作,并对第二和第三量子寄存器做受控非门,可得量子态1nni|i12(|0|0+|1|1)|0logl;3)受控访问数据结构 见式(10),可得1nni|i12(|0|0|xi+|1|1|yi)。此时,对第三和第四量子寄存器取偏迹,可得=12nnij|00|xi|xj|ij|+|11|yi|yj|ij|,(16)因此,可在时间复杂度 O(polylognl)内制备|CxxCxyCyxCyy|对应的量子态 和|Cxx00Cyy|对应的量子态。利用文献 19 中的定理,构造相应的。引理 1:令 A1,Ak为 k 个正定矩阵,相应的量子态形式可以在 O(polylognl)时间内制备,f1,fk是k个泰勒级数收敛的函数,ijnj=1表示 Ai的i个特征向量。那么,厄米操作fk(Ak)f1(A1)fk(Ak)f1(A1)可以在 Opolylognlkik2i(maxj|f1(1j)|minj|f1(1j)|)kl=2(maxj|f1(lj)|minj|f1(lj)|)2 的时间复杂度内实现,其中 i为矩阵 Ai的条件数,即Ai的最大特征值和最小特征值之间的比值。本研究中,f1(x):=x12,f2(x):=x12。显然满足引理 1 的条件。根据引理 1,将 fk(Ak)f1(A1)fk(Ak)f1(A1)中的量子操作作用在单位矩阵对应的量子态1nn1i=0|ii|上,即可得量子态。与文献 19 类似,为了避免在特征值指数小的情况下出现指数复杂度,采用文献 6 中使用的一种技术,即预先定义一个有效的条件数 keff,只对范围 1keff,1 内的特征值进行相位估计(通常取 keff=1),则有第 1 期王庆乐等:量子典型相关分析算法125maxj|f1(1j)|minj|f1(1j)|=maxj|f2(2j)|minj|f2(2j)|=k1/2eff,(17)因此,制备 的复杂度为 O(k3.5eff3polylognl)。步骤 2:对 做主成分分析根据定理 1,可实现和 相关的量子操作,根据量子主成分分析算法19,可以在量子态 上做相位估计。假设 的特征分解为=ii|ii|,(18)那么,由文献 20 可以得到=ii|ii|ii|.(19)量子主成分分析需要消耗的 的个数为 O(13),因此量子主成分分析的复杂度为 O(k3.5eff6polylognl)。在典型相关分析中,通常 是近似低秩矩阵,也就是说,仅有 d 个特征值较大,其余特征值接近于 0。此时,测量 的最后一个量子寄存器将以概率 O(1)获得 d 个较大的特征值中的任意一个,不妨记为 i,测量后的量子态即为其对应的特征向量|i。要得到所有的 d 个较大的特征值以及其对应的特征向量,测量次数应为 O(dlogd)。因此,总的复杂度为 O(dk3.5eff6polylognllogd).步骤 3:计算|wi=|Cxx00Cyy|12|i,i=0,1,d 1.(20)在复杂度 O(polylogn)内制备|Cxx00Cyy|对应的量子态,利用量子态求幂技术19,可以以复杂度O(t2polyllogn)实现 eit。根据 HHL 算法3,可以求得|wxiwyi|对应的量子态|wi,即|wi=12(|0|wxi+|1|wyi),(21)复杂度为 O(13polylogn)。综上,量子典型相关分析算法的复杂度为O(dk3.5eff6polylognllogd)。当d、k和1取值均为O(polylognl)时,与经典算法相比,量子算法在维度参数上具有指数加速效果。3结论典型相关分析是一种在实际生活中有很多应用的重要相关分析算法。利用量子算法的并行运算特性,提出了一种量子典型相关分析。将经典问题转化为求解一个矩阵的主成分问题以及矩阵的幂与向量相乘问题。在求矩阵的主成分问题中,结合量子主成分分析和量子判别分析中的子算法设计了所提出算法;在求矩阵的幂和向量相乘的问题中,应用 HHL 算法的思想并结合矩阵求幂算法,得到了很好的加速效果。在特定参数条件下,所提出算法相比经典典型分析具有指数加速效果。126量 子 电 子 学 报40 卷参参参考考考文文文献献献:1Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer J.SIAMJournal on Computing,1997,26(5):1484-1509.2Grover L K.A fast quantum mechanical algorithm for database search C.Proceedings of the Twenty-Eighth Annual ACMSymposium on Theory of Computing,1996:212-219.3Harrow A W,Hassidim A,Lloyd S.Quantum algorithm for linear systems of equations J.Physical Review Letters,2009,103(15):150502.4Wossnig L,Zhao Z K,Prakash A.Quantum linear system algorithm for dense matrices J.Physical Review Letters,2018,120(5):050502.5Clader B D,Jacobs B C,Sprouse C R.Preconditioned quantum linear system algorithm J.Physical Review Letters,2013,110(25):250504.6Rebentrost P,Mohseni M,Lloyd S.Quantum support vector machine for big data classification J.Physical Review Letters,2014,113(13):130503.7Liang J M,Shen S Q,Li M,et al.Variational quantum algorithms for dimensionality reduction and classification J.PhysicalReview A,2020,101(3):032323.8Wang G M.Quantum algorithm for linear regression J.Physical Review A,2017,96(1):012335.9Wang Y Z,Guan Z J,Guan H Y.Linear nearest neighbor synthesis algorithm of quantum circuits based on pre-evaluation J.Chinese Journal of Quantum Electronics,2021,38(1):75-85.王艺臻,管致锦,管海宇.基于预评价的量子电路线性最近邻综合算法J.量子电子学报,2021,38(1):75-85.10 Huang Y M,Lei H,Li X Y.A survey on quantum machine learning J.Chinese Journal of Computers,2018,41(1):145-163.黄一鸣,雷 航,李晓瑜.量子机器学习算法综述J.计算机学报,2018,41(1):145-163.11 Hotelling H.Relations between two sets of variates J.Biometrika,1936,28(3/4):321-377.12 Hardoon D R,Szedmak S,Shawe-Taylor J.Canonical correlation analysis:An overview with application to learning methodsJ.Neural Computation,2004,16(12):2639-2664.13 Sun Q S,Zeng S G,Wang P A,et al.The theory of canonical correlation analysis and its application to feature fusion J.Chinese Journal of Computers,2005,28(9):1524-1533.孙权森,曾生根,王平安,等.典型相关分析的理论及其在特征融合中的应用J.计算机学报,2005,28(9):1524-1533.14 Tenenhaus A,Philippe C,Frouin V.Kernel generalized canonical correlation analysis J.Computational Statistics&DataAnalysis,2015,90(4):114-131.15 Wang F S,Zhang D Q.A new locality-preserving canonical correlation analysis algorithm for multi-view dimensionalityreduction J.Neural Processing Letters,2013,37(2):135-146.16 Wang S,Lu J F,Gu X J,et al.Unsupervised discriminant canonical correlation analysis based on spectral clustering J.Neurocomputing,2016,171:425-433.17 Hu W X,Lin D D,Cao S L,et al.Adaptive sparse multiple canonical correlation analysis with application to imaging(epi)genomics study of schizophrenia J.IEEE Transactions on Biomedical Engineering,2018,65(2):390-399.18 Zhuang X W,Yang Z S,Cordes D.A technical review of canonical correlation analysis for neuroscience applications J.Human Brain Mapping,2020,41(13):3807-3833.19 Cong I,Duan L M.Quantum discriminant analysis for dimensionality reduction and classification J.New Journal of Physics,2016,18(7):073011.20 Lloyd S,Mohseni M,Rebentrost P.Quantum principal component analysis J.Nature Physics,2014,10(9):631-633.