量子计算展示了其相对经典计算的强大优势[1-2].在处理特定的问题时，如大数质因数分解[3]、无结构数据搜索[4]、稀疏线性方程组求解[5]和低秩矩阵主成分分析[6]，采用量子计算的方式具有比经典计算方式低得多的复杂度.近年来，一些研究人员将量子强大的计算能力用在处理经典计算机上具有较高复杂度的机器学习问题，取得了一系列成果，包括量子回归算法[7]、量子支持向量机[8]、量子生成对抗网络[9-10]、量子神经网络和量子数据挖掘[11]等.
子空间学习是机器学习的重要部分.现实世界的数据大多数是以高维的形式出现，而决定计算任务——例如分类和回归——结果的有效维度往往很低.由于直接处理高维数据不仅需要消耗大量计算资源，还会导致维数灾难(the curse of dimensionality)问题，因此子空间学习被提出，用来把数据集从高维降到低维，同时保持数据潜在的结构.人脸识别的结果表明，通过子空间学习进行降维，可以显著地提高算法的性能[12].尽管子空间学习可以部分解决高维数据的学习问题，但子空间学习本身通常也需要很高的复杂度，因此如何降低子空间学习的复杂度是一个很有实际意义的问题.一个自然而然的想法是将量子计算应用于子空间学习，以达到更低的算法复杂度.
常用的子空间学习算法包括主成分分析(principal components analysis,PCA)[13]、线性判别分析(linear discriminant analysis,LDA)[14]、局部保持投影(locality preserving projections,LPP)[12]和邻域保持嵌入(neighborhood preserving embedding,NPE)[15]等.子空间学习算法如LDA,LPP和NPE，通常需要进行稠密矩阵的特征分解，这往往需要消耗较高的计算资源.为了降低计算资源，2007年Cai等人[16]提出了谱回归降维框架，该框架包含了很多现有的子空间学习算法，如LDA，LPP和NPE.在同一篇文章中，针对结合标签信息来构造对应图的子空间学习，Cai等人提出了高效谱回归.Cai等人提出可利用权重矩阵的特殊结构，结合格拉姆-施密特正交化来得到稠密矩阵的特征向量，而不需要对稠密矩阵进行特征分解，从而把复杂度从维数的立方降低为维数的一次方.另外，因为引入了线性回归，所以谱回归中也可以很自然地加入正则化参数，使得算法可用于数据矩阵是病态矩阵的情况.
在量子领域，Lloyd等人[6]率先提出了量子主成分分析算法(quantum principal component analysis algorithm,QPCA)，算法相对经典算法具有指数加速效果.需要指出的是，尽管该算法被称为QPCA算法，但实际上如果要维持量子算法的加速效果，该算法只能用来得到低秩(或者近似低秩)矩阵的较大的特征值，以及以量子态形式得到对应的特征向量；另外，如果矩阵有重特征值，那么我们无法通过量子主成分分析得到重特征值对应的一组特征向量，而只能得到特征向量的叠加态.随后，Yu等人基于量子PCA算法，提出了量子PCA降维算法，当降维后数据的维数为训练数据维数的对数时，他们的量子算法相对经典算法实现了指数级的加速[17].Cong等人实现了量子LDA算法，与经典算法相比有指数级的加速效果[18].Meng等人基于谱回归降维框架[16]，首次提出了正则化子空间学习的量子谱回归算法(MYXZ算法，以作者姓名首字母命名)，并在降维数据的项数m和数据的特征数n满足m=O(lb n)时，算法具有多项式加速效果[19].尽管如此，MYXZ算法仍然存在有待改进的地方.首先，MYXZ算法在算法的第一步，即求一般特征值问题时用了稀疏哈密顿量模拟，当处理的矩阵是稀疏矩阵时，算法具有良好的加速效果，但实际应用中存在很多矩阵不稀疏的例子，例如LDA，此时用稀疏哈密顿量模拟没有加速效果.其次，如果算法第一步的解中有相同的特征值，也会导致MYXZ算法无法得到相应的特征向量(只能得到特征向量的叠加态)而导致后续步骤出错.最后，MYXZ算法的加速基于假设m=O(lb n)，其中m为数据的项数，n为数据的特征数.因为谱回归的原始文献[16]的重点在于把算法复杂度中的因子m3降至m，而对于m=O(lb n)的情况，谱回归本身只有很小的加速效果，因此我们认为m=O(n)是更符合实际情况的假设.
本文首先对MYXZ算法进行了细致分析，并指出了算法的局限性.然后，我们提出了一个改进算法，该算法采用了量子奇异值估计技术(quantum singular value estimation,QSVE)[20]，而不是稀疏量子主成分分析来求解一般特征值问题，在处理稠密矩阵特征值问题时，QSVE具有更低的复杂度.当m=O(n)时，我们的改进算法相对经典算法有多项式加速效果；当算法的第1步涉及的矩阵是稠密矩阵时，我们的改进算法相对MYXZ算法有多项式加速效果.其次，针对结合标签信息来构造对应图的子空间学习算法，例如LDA和带标签的LPP,NPE，我们提出了相应的量子算法.我们把文献[16]中提出的高效算法中复杂度较高的岭回归部分设计成量子算法，并行得到多个岭回归结果；而复杂度较低的部分(即格拉姆施密特正交化)仍然采用原算法实现.这样做的好处在于既规避了稠密矩阵特征分解的问题，也利用了量子的加速效果.另外，为了算法的完整性，我们给出了对新输入数据进行降维的实现方式.当m=O(n)时，我们的算法相对经典的高效谱回归算法具有多项式加速效果.
1 正则化子空间学习的谱回归
在本节中，我们将对正则化子空间学习的谱回归进行回顾，并介绍其复杂度.
1.1 谱回归
假设有m张人脸图像，表示为
n，令X=(x1,x2,…,xm).我们要做的是对这些图像数据进行降维处理，降维后数据矩阵表示为Y=(y1,y2,…,ym).为了对新输入数据进行降维，以及对测试集的数据进行检验，通常需要输出降维矩阵A，对新输入数据x，降维后数据记为yx=ATx.
令G表示由m个顶点构成的图，每个顶点对应一张人脸图像即xi，W为一个m×m的权重矩阵，其元素表示图G中顶点i和顶点j之间的权重.谱回归是一个降维算法的框架，通过W矩阵的不同选取方式，能得到不同的降维算法，如线性判别分析、局部保持投影和邻域保持嵌入.谱回归的提出是为了避免降维算法中复杂度较高的稠密矩阵特征分解.
谱回归主要包含3个步骤：
1)求解最大特征向量问题
Wy=λDy，
(1)
其中，D为对角矩阵，
得到最大的c-1个特征值对应的特征向量y(1),y(2),…,y(c-1)，c为类别个数.
2)求解c-1个最小二乘问题
(2)
其中,
表示向量y(i)的第j个元素，i∈{1,2,…,c-1}.
3)对新数据x进行降维，令A=(a1,a2,…,ac)，则降维后的坐标为
yx=ATx.
当样本数m小于特征数n时，优化问题(2)是病态的，一种常见的做法是采用岭回归的方式，引入正则化参数α，即求解优化问题：
此时ai的解析解为
ai=(XXT+αI)-1Xy(i).
引入正则化参数的谱回归被称为正则化子空间学习的谱回归.
在文献[16]中，作者提出一种高效的谱回归求解方法.对于结合标签信息来构造对应图的降维算法，如LDA以及有监督的LPP和NPE，其最大特征向量问题(即式(1))的求解是平凡的.不妨假设数据是按标签信息排列的，则
其中W(t)是mt×mt的矩阵，mt为第t个类别的样本数，此时可以直接给出式(1)的最大特征值1对应的c个特征向量，即
另外，显然全1向量1=(1,1,…,1)T也是式(1)中最大特征值1对应的特征向量.因为对所有的W，1都是式(1)中特征值1对应的特征向量，因此1并不包含关于问题的任何信息.为了去除和1相关的冗余信息，文献[16]中提出的方法是取1为第1个正交向量，其余c-1个特征向量由y(i)通过格拉姆-施密特正交化得到.最后去掉1，就得到了我们想要的c-1个相互正交的特征向量，也即式(1)的解.
1.2 谱回归的复杂度
根据文献[16]中的算法，回归算法的第1步的复杂度主要来源于格拉姆-施密特正交化，复杂度为
第2步做c-1次岭回归的复杂度为s(c-1)(2mn+3m+5n)，其中s为迭代次数，岭回归的收敛很快，因此s通常取值较小；第3步矩阵向量乘法的复杂度为O(cn).因此总算法复杂度为O(c2m+cmns).
2 正则化子空间学习的量子谱回归
本节将对正则化子空间学习的量子谱回归进行回顾，并对算法进行分析，给出算法复杂度.
2.1 量子谱回归
2019年，Meng等人提出了正则化子空间学习的量子谱回归算法[19](MYXZ算法).该算法没有利用文献[16]中的核心思想，即对于结合标签信息来构造对应图的降维算法，其最大特征向量问题的求解(式(1))是平凡的，而是直接用量子主成分分析[6]的方式来对矩阵进行特征分解.
MYXZ算法主要包含2个步骤：
1)用稀疏矩阵量子主成分分析和量子矩阵向量乘法来求式(1)的解y(1),y(2),…,y(c-1).
MYXZ算法假设矩阵
事先被存储在一个树状的量子存储器(QRAM)中，其中Im为m×m的矩阵.用量子算法(即量子主成分分析)求最大特征向量问题：
得到的c-1个最大特征值对应的特征向量(量子态形式)表示为
则式(1)的解
可通过量子矩阵向量乘法得到[5].
2)用量子算法求
ai=(XXT+αI)-1Xy(i).
MYXZ算法假设矩阵X事先存储在一个树状的QRAM中，基于量子稠密线性方程组求解技术[16]，设计出量子稠密矩阵岭回归技术，可直接用于求ai.
MYXZ算法没有考虑算法的第3步，也即针对一个新输入的数据x，输出其降维后坐标yx=Ax.
2.2 算法分析
本节将结合文献[19]中的假设，对算法及其复杂度进行分析.
文献[19]认为矩阵
是稀疏矩阵，其稀疏度用sL表示.第1步的量子主成分分析中量子模拟部分采用的是稀疏哈密顿量模拟的方式.稀疏哈密顿量模拟的复杂度为
表示一些增长慢的项被省略掉了)[5].注意到，矩阵通常不是低秩矩阵，所以在量子主成分分析测量时，测量一次得到最大的c个特征值中的一个的概率为
需要指出的是，文献[19]并没有考虑测量的概率，导致算出来的复杂度比实际的复杂度低)，引入幅度放大，量子主成分分析的复杂度为
(我们用polylb(m)来表示poly(lb m)，以简化符号.polylb(m)来源于对量子态
|j〉的制备)，算法的输出为
文献[19]没有明确给出
的量子算法及其复杂度，尽管看起来这部分算法很直接，且复杂度低于量子主成分分析部分，为了完整性，我们给出具体的算法并分析其复杂度.类似于矩阵的存储假设，我们假设D的元素是存储在QRAM中的.因为D是对角矩阵，且要得到
需要先得到D，因此这个假设比矩阵
的假设弱.此时输入
直接调用QRAM查询(复杂度为O(lb m))可得量子态
通过受控旋转[5](复杂度可忽略)和测量(平均测量次数为O(κD)，其中κD为矩阵D的条件数，即最大特征值和最小特征值的比值.通过幅度放大，调用QRAM查询的次数降低为
可得量子态
再次调用QRAM对第2量子寄存器进行逆运算，可得
因此矩阵向量乘法的复杂度为
在实际问题中，κD通常取值较小，因此这个复杂度相对于量子主成分分析部分是可以忽略的.
综上，算法的第1步总复杂度为
算法的第2步对稠密线性方程组技术进行了推广，应用于岭回归求解，这一步的算法的复杂度为
其中κ为矩阵X的条件数.因此算法的总复杂度为
作为对比，经典算法的复杂度为O(c2m+cmns).当
因为c≪m[16]，sL≤m=O(lb n)，此时算法相对经典算法在n上有指数加速效果.当
时，因为c≪m[16]，不妨令c=O(lb m)，若sL=O(lb n)，那么算法相对经典算法有多项式加速效果；若
(这种情况常见于LDA)，那么算法的复杂度比经典算法的复杂度更高.
3 改进的量子谱回归
在实际应用中，往往样本数量m和提取的特征个数n的规模是相差不大的，另外，在谱回归的原始论文中[16]，谱回归算法的优势在于降低了复杂度中参数m的次数.如果m≪n，谱回归的加速效果并不明显.因此在改进的算法中，在其他参数假设不变的前提下，我们希望在m=O(n)时，量子算法相对经典算法有显著加速效果.
在对MYXZ算法复杂度的分析中，我们发现，在较多的情况下，矩阵并不是一个稀疏矩阵(如在LDA中，有csL≥m，通常认为c取值较小[16]，不妨令c=O(lb m)，此时有
在主成分分析步骤中采用稀疏矩阵模拟的方式并没有加速效果.
针对这种情况，我们的改进算法不采用稀疏矩阵模拟的方式来进行主成分分析，而是直接用量子奇异值估计[20](QSVE)来得到相应的特征向量.QSVE算法在处理稠密矩阵时具有更低的复杂度.具体地，类似于MYXZ算法，假设的信息存储在树状的QRAM中.那么可以制备
不妨令
那么根据QSVE[20]可得：
算法复杂度为
其中
令
则有
此时复杂度为
测量第4寄存器，以
的概率测得较大的λi，此时可得对应的量子态
可通过振幅放大，重复次数降低为
因此第1步的总复杂度为
结合MYXZ算法的第2步，总算法复杂度为
对比经典算法复杂度O(csmn+c2n)，当
时，算法具有多项式加速效果.对比MYXZ算法，我们算法在m=O(n)且矩阵不是稀疏矩阵时，具有更低的复杂度.
4 高效谱回归的量子算法
在文献[16]中，Cai等人针对结合标签信息来构造对应图的降维算法，如有监督的局部保持投影和邻域保持嵌入，提出了一个高效的实现方式.对于这类降维算法，式(1)的最大特征值1是c重特征值，因而MYXZ算法无法进行处理.我们提出了这类子空间学习问题的量子谱回归算法.我们的算法中也用到了MYXZ中的部分过程.
在MYXZ算法中，假设矩阵的信息被存储在树状的QRAM中，而在实际情况中，通常我们并不会事先知道矩阵的信息.特别在一些问题中，矩阵的计算较为复杂，如带标签的NPE算法，W由几个矩阵的乘积及求和得到，而
此时如果直接进行存储假设，而不计算其复杂度，对与之作对比的经典算法不公平.我们的算法仅假设数据矩阵X被按标签顺序存储在树状的QRAM中.
4.1 算法过程
考虑到量子主成分分析的局限性，我们直接采用经典的方式来求式(1)的解.我们的算法步骤为：
1)令第1个特征向量为全1向量(1,1,…,1)T，通过对
进行格拉姆-施密特正交化，得到c-1正交的特征向量，作为式(1)的解，记为y(1),y(2),…,y(c-1).
2)把y(1),y(2),…,y(c-1)存储到QRAM中，制备量子态
3)对第2量子寄存器，执行稠密矩阵岭回归量子算法，得
4)针对新输入的量子态|x〉，用量子低秩矩阵向量乘法，来求其降维后量子态|y〉.
我们算法的第4步即对新输入的数据进行降维，这正是子空间学习的目的.MYXZ算法没有给出算法的降维过程，为了算法的完整性，我们将给出降维过程以及其复杂度分析.
4.2 算法分析
4.1节所述的步骤1为经典步骤，复杂度为
在4.1节所述的步骤2中，我们先把y(1),y(2),…,y(c-1)存储到c-1个QRAM中，因为元素个数为m(c-1)，因此QRAM存储的执行次数为O(mc).通过调用存储y(i)的QRAM，我们可以制备量子态
其中
表示向量y(i)的第j+1个元素.添加辅助比特进行受控旋转，得
其中Cz为绝对值不小于
的绝对值的一个常数，即
对第2寄存器做逆计算，并测量辅助寄存器，若测量结果为1，即得量子态|y(i)〉.可以看到，对于一般的量子态，测量结果为1的概率
因此需要重复制备量子态|ψ1〉的次数为O(m2).在算法中引入幅度放大，重复制备次数可以降低为O(m).因此，制备量子态|y(i)〉的复杂度为O(mlb m).进而，制备|ψ〉的复杂度为O(cmlb c lb m).其中因子lb c来源于查找标签i所对应的存储位置，c来源于读取QRAM c-1次.需要指出的是，QRAM只需要存储一次，就可以进行多次读取.
在4.1节所述的步骤3中，我们采用MYXZ算法中稠密矩阵岭回归算法来求|φ〉.具体地，类似于MYXZ算法的假设，假设矩阵X事先存储在一个树状的QRAM中，再在第2寄存器上直接执行量子稠密矩阵岭回归算法，即得量子态|φ〉，复杂度和MYXZ算法相应步骤一致，为
需要注意的是，这个复杂度并没有考虑对|ψ〉的制备，因为需要进行O(κ)次的调用，因此这部分的复杂度为O(cκmlb c lb m).
为了方便对4.1节所述的步骤4的分析，我们定义对数据的量子访问[21]：
定义1[21].如果存在以下变换可以在复杂度T内实现，那么称我们可以通过量子访问矩阵A∈n×m：
|i〉|0〉→|i〉|Ai〉,
其中,i∈{1,2,…,n}，Ai表示矩阵A的第i列构成的向量.
需要注意的是，4.1节算法步骤2～3可以实现|i〉|0〉→|i〉|Ai〉，但该过程不可逆(涉及到测量)，我们可以把这些过程转化为可逆的[22]，而复杂度只有常数倍的增长.在我们的算法中，
因此制备
是平凡的.因此我们有对数据矩阵的量子访问，其中
额外的复杂度为O(cκmlb clb m).进而，利用量子访问，我们可以实现矩阵
的
n)
,0)块编码[23]，复杂度为
根据引理1，我们可得生成量子态
的复杂度(引理1中 γ取常数，
为
引理1[23]. 令A为N×N的复矩阵，|b〉为满足
量子态.假设制备|b〉的复杂度为Tb，A的(α,a,0)编码可以在TA复杂度内实现，那么有量子算法可以以精度ε生成量子态
复杂度为
综上，算法的总复杂度为
相比经典算法的复杂度O(c2m+cmns)，当
时，我们提出的量子算法具有多项式加速效果.
相关算法的复杂度对比和适用条件如表1所示.需要注意的是，我们没有把降维过程(即4.1节中的算法步骤4)的复杂度列在表中，因此表中量子高效谱回归的总复杂度比上面算出来的复杂度稍低，但并不影响对比结果.
Table 1 Comparison of Complexity and Applicable Conditions of Classical and Quantum Spectral Regression Algorithms
表1 经典和量子谱回归算法的复杂度和适用条件对比
算法最大特征问题岭回归适用条件总复杂度量子算法Ocms4Lεpolylb(m) Ocmκ2εpolylb(m+n) 特征值不同,稀疏Ocms4Lεpolylb(m)+cmκ2εpolylb(m+n) 经典算法mc2-13c3O(csmn)整合标签信息的降维算法(特征值相同)O(csmn+c2m)改进算法(第3节)Omcεpolylb(m) Ocmκ2εpolylb(m+n) 特征值不同Ocmκ2εpolylb(m+n) 新算法(第4节)mc2-13c3Omκ2εpolylb(m+n)+cκmlbclbm 整合标签信息的降维算法(特征值相同)Oc2κ2mεpolylb(m+n)
5 结 论
在本文中，我们重新分析了MYXZ算法的细节，并纠正了其复杂度(并不影响MYXZ算法的结论).针对MYXZ算法的局限性，即在m=O(n)时，只能在为稀疏矩阵的情形下才有量子加速，我们提出了一个改进算法.改进算法采用QSVE来得到的特征向量，因而复杂度不受是否稀疏的影响，算法在m=O(n)且为稠密矩阵的情形下相对经典算法有多项式加速效果.另外，针对文献[16]中提出的高效谱回归算法，我们提出了其量子版本的算法.我们算法解决的问题并不能用MYXZ算法来解决，因为求解的问题有c-1重特征值.实际上，如果特征值问题(1)的解中有重根，即有2个以上特征向量共享一个特征值，那么MYXZ算法将无法通过量子主成分分析得到相应的特征向量(只能得到特征向量的叠加态)而导致后续步骤出错.我们算法的优势在于把经典计算机上复杂度较高的部分用量子算法进行降维，而复杂度较低的部分保持原有经典算法.我们的算法设计思想不仅对子空间学习算法，而且对其他类型的机器学习算法都具有一定的参考价值.
[1]Biamonte J,Wittek P,Pancotti N,et al.Quantum machine learning[J].Nature,2017,549(7671):195-202
[2]Wang Yongli,Xu Qiuliang.Principle and research progress of quantum computation and quantum cryptography[J].Journal of Computer Research and Development,2020,57(10):2015-2026(王永利,徐秋亮.量子计算与量子密码的原理及研究进展综述[J].计算机研究与发展,2020,57(10):2015-2026)
[3]Shor P.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal on Computing,1997,26(5):1484-150
[4]Grover L K.A fast quantum mechanical algorithm for database search[C] //Proc of the 28th Annual ACM Symp on Theory of Computing.New York:ACM,1996:212-219
[5]Harrow A W,Hassidim A,Lloyd S.Quantum algorithm for linear systems of equations[J].Physical Review Letters,2009,103(15):No.150502
[6]Lloyd S,Mohseni M,Rebentrost P.Quantum principal component analysis[J].Nature Physics,2014,10(9):631-633
[7]Wiebe N,Braun D,Lloyd S.Quantum algorithm for data fitting[J].Physical Review Letters,2012,109(5):No.050505
[8]Rebentrost P,Mohseni M,Lloyd S.Quantum support vector machine for big data classification[J].Physical Review Letters,2014,113(13):No.130503
[9]Lloyd S,Weedbrook C.Quantum generative adversarial learning[J].Physical Review Letters,2018,121(4):No.040502
[10]Situ Haozhen,He Zhimin,Wang Yuyi,et al.Quantum generative adversarial network for generating discrete distribution[J].Information Sciences,2020 (538):193-208
[11]Yu Chaohua,Gao Fei,Wang Qingle,et al.Quantum algorithm for association rules mining[J].Physical Review A,2016,94(4):No.042311
[12]He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacianfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340
[13]Hotelling H.Relations between two sets of variates[J].Biometrika,1936,28(3/4):321-377
[14]Fisher R A.The use of multiple measurements in taxonomic problems[J].Annals of Eugenics,1936,7(2):179-188
[15]He Xiaofei,Cai Deng,Yan Shuicheng,et al.Neighborhood preserving embedding[C] //Proc of the 10th IEEE Int Conf on Computer Vision.Piscataway,NJ:IEEE,2005:1208-1213
[16]Cai Deng,He Xiaofei,Han Jiawei.Spectral regression for efficient regularized subspace learning[C] //Proc of IEEE 11th Int Conf on Computer Vision.Piscataway,NJ:IEEE,2007:1-8
[17]Yu Chaohua,Gao Fei,Lin Song,et al.Quantum data compression by principal component analysis[J].Quantum Information Processing,2019,18(8):No.249
[18]Cong I,Duan Luming.Quantum discriminant analysis for dimensionality reduction and classification[J].New Journal of Physics,2016,18(7):No.073011
[19]Meng Fanxu,Yu Xutao,Xiang Ruiqing,et al.Quantum algorithm for spectral regression for regularized subspace learning[J].IEEE Access,2019,7:4825-4832
[20]Kerenidis I,Prakash A.Quantum recommendation systems[C] //Proc of the 8th Innovations in Theoretical Computer Science Conf.Dagstuhl:Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,2017,67:49:1-49:21
[21]Kerenidis I,Landman J.Quantum spectral clustering[J].Physical Review A,2021,103(4):No.042415
[22]Kerenidis I,Landman J,Luongo A,et al.q-means:A quantum algorithm for unsupervised machine learning[C] //Advances in Neural Information Processing Systems 32.Vancouver:Curran Associates,Inc.,2019:1-11
[23]Chakraborty S,Gilyén A,Jeffery S.The power of block-encoded matrix powers:Improved regression techniques via faster Hamiltonian simulation[C] //Proc of the 46th Int Colloquium on Automata,Languages,and Programming.Dagstuhl:Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,2019:33:1-33:14
