基于最大方差展开的量子非线性降维

最大方差展开算法是在流形局部等距的基础上提出的一种非线性降维算法.然而,在处理大规模数据集时它需要大量的计算成本.为此,本文提出了一种高效的量子最大方差展开算法.首先,提出了一个量子矩阵平方根算法,它可以指数加速地实现矩阵开平方,从而有效地获得拉普拉斯矩阵的密度算子.然后,在此基础上给出了完整的量子降维算法,利用哈密顿模拟和相位估计将原始高维数据映射到低维数据空间.最后,时间复杂度分析表明,本文所提量子降维算法相较于经典算法在维度上实现了指数加速,在样本数量上实现了多项式加速.