量子谱回归算法

来源：计算机研究与发展杂志2021年第9期北京时间：

作者：潘世杰,高飞,万林春,秦素娟,温巧燕,

摘要：子空间学习是机器学习领域的重要研究方向.为了降低子空间学习的复杂度，Cai等人提出了谱回归降维框架，并针对结合标签构造对应图的子空间学习提出了高效谱回归.近年来，量子计算的发展使进一步降低子空间学习算法的复杂度成为了可能.Meng等人率先提出了量子谱回归算法(MYXZ算法).MYXZ算法用了稀疏哈密顿量模拟技术来处理由权重矩阵生成的矩阵，但这个矩阵在较多的情况下是稠密矩阵.针对这种情况，指出了MYXZ算法的局限性，提出了一个改进的量子谱回归算法.改进算法采用了量子奇异值估计技术，在处理稠密矩阵时相对MYXZ算法有多项式加速.另外，提出了一个新的量子算法，对经典的高效谱回归进行加速.新算法能处理的这类问题是MYXZ算法无法处理的.新算法利用了量子岭回归和量子矩阵向量乘技术，在相同的参数条件下相对经典算法具有多项式加速效果.

关键词：量子算法, 量子机器学习, 谱回归, 子空间学习, 稠密矩阵,