1、第 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)摘要:典型相关分析是一种重要的数据处理方法,用于处理
2、随机向量之间的相互依赖关系。然而,经典的典型相关分析算法的复杂度对数据维度是多项式依赖的,致使该类算法并不适用于分析在大数据时代下规模呈指数增长的数据。针对经典的典型相关分析算法的这种缺陷,提出了一种量子典型相关分析算法。该算法把典型相关分析所涉及的优化问题转化为适合用量子计算技术处理的代数问题,并采用量子主成分分析技术进行求解,从而降低了典型相关分析算法的复杂度。在特定的参数条件下,所提算法可实现在数据维度上的指数加速,符合当今实际数据处理对该算法的需求。关 键 词:量子算法;量子主成分分析;相关分析;指数加速中 图 分 类 号:O413文 献 标 识 码:A文章编号:1007-5461(2
3、023)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
4、 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 compl
5、exity 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
6、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
7、,thereby reducing the cost of canonical correlation analysis基金项目:国家自然科学基金(61801126),北京邮电大学网络与交换技术国家重点实验室开放项目(SKLNST-2021-1-05),中国科学技术大学中国科学院量子信息重点实验室开放项目(KQI201902),信息网络安全公安部重点实验室开放课题(C21605),中央高校基本科研业务(2020MS014)作者简介:王庆乐(1987-),女,山东临沂人,博士,副教授,主要从事量子密码、量子信息论、量子计算方面的研究。E-mail:收稿日期:20210406;修改日期:20210
8、513通信作者。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 compone
9、nt analysis;correlation analysis;exponential acceleration0引言量子计算在处理某些特定问题时有比经典计算更强的计算能力,如质因数分解1、非结构化数据搜索2和矩阵计算问题35。近年来,随着量子计算机的发展,量子机器学习(QML)受到了广泛关注。QML 研究的一个重要方向是设计量子算法来加速机器学习,包括数据分类6,7和线性回归等810。严格来说,大部分机器学习算法实际上也是统计分析算法,统计分析中的一种重要方法为典型相关分析。实际上,当需要分析和研究两组变量之间的关系时,通常会用到典型相关分析。例如,为了研究财政政策实施以后对经济发展的影响
10、,需要考察有关财政政策的一系列指标(如财政支出总额、财政赤字、国债发行额、税率等)与经济发展的一系列指标(如国内生产总值、就业率等两组变量)之间的相关程度。典型相关分析方法最初由 Hotelling11在 1936 年提出。2004 年,Hardoon 等12对该方法进行了综述,并提出了其在学习方法上的应用。2005 年,Sun 等13提出把典型相关分析用于特征融合。近年来,典型相关分析研究不断发展,其变体也相继被提出,包括基于核理论的典型相关分析14、基于流形结构的典型相关分析15、基于监督学习的典型相关分析16、稀疏典型相关分析等17,18。当数据量很大时,典型相关分析算法运算速度很慢,耗
11、时严重,因此其不适用于大数据时代。本文利用量子计算的优势降低典型相关分析算法的复杂度,并提出了量子典型相关分析算法。所提出量子算法在特定参数条件下,相对经典典型相关分析在维度上有指数加速效果。1典型相关分析1.1典典典型型型相相相关关关分分分析析析的的的提提提出出出典型相关分析的目的是寻求两组变量中每一组变量的线性组合,使得两组变量的线性组合之间的相关性最大化。一般的相关性分析依赖于变量的坐标系,即使两组多维变量之间本质上存在非常强的线性关系,坐标系选取不恰当也会导致线性关系不可见12。典型相关分析通过研究两组综合指标之间的关系来研究变量之间的线性关系,可用于挖掘一般相关性分析中的不可见关系。
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出发,计算第二对典型向
13、量,即寻找与 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,wywTxCxywywTxCxxwxw
14、TyCyywy.(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问问问题题题转转转化化
15、化显然|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 期王庆
16、乐等:量子典型相关分析算法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)以及每一列的二范数组成的向量对
