量子典型相关分析算法

王庆乐, 薛雪, 李元诚∗

(1 华北电力大学控制与计算机工程学院, 北京 102206;2 北京邮电大学网络与交换技术国家重点实验室, 北京 100876;3 中国科学技术大学量子信息重点实验室, 安徽 合肥 230026)

0 引 言

量子计算在处理某些特定问题时有比经典计算更强的计算能力,如质因数分解[1]、非结构化数据搜索[2]和矩阵计算问题[3−5]。近年来,随着量子计算机的发展,量子机器学习(QML)受到了广泛关注。QML 研究的一个重要方向是设计量子算法来加速机器学习,包括数据分类[6,7]和线性回归等[8−10]。

严格来说,大部分机器学习算法实际上也是统计分析算法,统计分析中的一种重要方法为典型相关分析。实际上,当需要分析和研究两组变量之间的关系时,通常会用到典型相关分析。例如,为了研究财政政策实施以后对经济发展的影响,需要考察有关财政政策的一系列指标(如财政支出总额、财政赤字、国债发行额、税率等)与经济发展的一系列指标(如国内生产总值、就业率等两组变量)之间的相关程度。典型相关分析方法最初由Hotelling[11]在1936 年提出。2004 年,Hardoon 等[12]对该方法进行了综述,并提出了其在学习方法上的应用。2005 年,Sun 等[13]提出把典型相关分析用于特征融合。近年来,典型相关分析研究不断发展,其变体也相继被提出,包括基于核理论的典型相关分析[14]、基于流形结构的典型相关分析[15]、基于监督学习的典型相关分析[16]、稀疏典型相关分析等[17,18]。当数据量很大时,典型相关分析算法运算速度很慢,耗时严重,因此其不适用于大数据时代。

本文利用量子计算的优势降低典型相关分析算法的复杂度,并提出了量子典型相关分析算法。所提出量子算法在特定参数条件下,相对经典典型相关分析在维度上有指数加速效果。

1 典型相关分析

1.1 典型相关分析的提出

典型相关分析的目的是寻求两组变量中每一组变量的线性组合,使得两组变量的线性组合之间的相关性最大化。一般的相关性分析依赖于变量的坐标系,即使两组多维变量之间本质上存在非常强的线性关系,坐标系选取不恰当也会导致线性关系不可见[12]。典型相关分析通过研究两组综合指标之间的关系来研究变量之间的线性关系,可用于挖掘一般相关性分析中的不可见关系。

具体地,考虑两组多变量随机向量:X= [x0,x1,··· ,xn−1]和Y= [y0,y1,··· ,ym−1],其中xi和yj均为l维向量。定义一个线性组合wx,使得矩阵X列向量之间的一个线性组合为zx=Xwx。同理,可定义zy=Ywy。

典型相关分析通过选择合适的wx和wy,使投影后的向量具有最大的相关性,即最大化函数

1.2 典型相关分析的求解及其复杂度

记[x,y]的协方差矩阵为C(x,y),则

经典算法求解(4)式转化为求一般特征值问题,计算复杂度为O(poly(nml)),其中n、m分别是随机向量X、Y中的随机变量个数,l是随机变量xi和yj的维度。

2 量子典型相关分析

2.1 问题转化

2.2 量子典型相关分析算法设计

量子算法的输入是矩阵X= [x0,x1,··· ,xn−1]和Y= [y1,y2,··· ,ym]。简单起见,令n=m。实际上,如果n>m,可令Y= [y1,y2,··· ,ym,y1,y2,··· ,yn−m]。由于要找的是一个向量之间的线性组合,因此对Y进行这样的处理不会影响最终结果。

不妨假设向量xi和yj(i,j∈{0,1,··· ,n−1})均为归一化向量,即

假设输入存储在一个经典的数据结构中,那么量子访问数据结构可以高效创建矩阵X和Y的每一列对应的量子态

以及每一列的二范数组成的向量对应的量子态|˜X〉和|˜Y〉,创建这些量子态的复杂度均为O[polylog(mnl)]。

步骤2:对ρ 做主成分分析

根据定理1,可实现和ρ 相关的量子操作,根据量子主成分分析算法[19],可以在量子态ρ 上做相位估计。假设ρ 的特征分解为

那么,由文献[20]可以得到

步骤3:计算

3 结 论

典型相关分析是一种在实际生活中有很多应用的重要相关分析算法。利用量子算法的并行运算特性,提出了一种量子典型相关分析。将经典问题转化为求解一个矩阵的主成分问题以及矩阵的幂与向量相乘问题。在求矩阵的主成分问题中,结合量子主成分分析和量子判别分析中的子算法设计了所提出算法;在求矩阵的幂和向量相乘的问题中,应用HHL 算法的思想并结合矩阵求幂算法,得到了很好的加速效果。在特定参数条件下,所提出算法相比经典典型分析具有指数加速效果。