潘世杰 高 飞 万林春 秦素娟 温巧燕

1(网络与交换技术国家重点实验室(北京邮电大学) 北京 100876) 2(密码科学技术国家重点实验室 北京 100878)

量子计算展示了其相对经典计算的强大优势[1-2].在处理特定的问题时，如大数质因数分解[3]、无结构数据搜索[4]、稀疏线性方程组求解[5]和低秩矩阵主成分分析[6]，采用量子计算的方式具有比经典计算方式低得多的复杂度.近年来，一些研究人员将量子强大的计算能力用在处理经典计算机上具有较高复杂度的机器学习问题，取得了一系列成果，包括量子回归算法[7]、量子支持向量机[8]、量子生成对抗网络[9-10]、量子神经网络和量子数据挖掘[11]等.

子空间学习是机器学习的重要部分.现实世界的数据大多数是以高维的形式出现，而决定计算任务——例如分类和回归——结果的有效维度往往很低.由于直接处理高维数据不仅需要消耗大量计算资源，还会导致维数灾难(the curse of dimensionality)问题，因此子空间学习被提出，用来把数据集从高维降到低维，同时保持数据潜在的结构.人脸识别的结果表明，通过子空间学习进行降维，可以显著地提高算法的性能[12].尽管子空间学习可以部分解决高维数据的学习问题，但子空间学习本身通常也需要很高的复杂度，因此如何降低子空间学习的复杂度是一个很有实际意义的问题.一个自然而然的想法是将量子计算应用于子空间学习，以达到更低的算法复杂度.

常用的子空间学习算法包括主成分……