量智信息中心_量科网

谱方法是处理带有“尖峰”高斯张量的张量主成分分析（PCA）的主要方法之一。这些方法利用了指数高维向量空间中线性算子的谱特性。参考文献1表明，量子算法不仅能实现指数级空间节省，还能获得相对于经典算法的四次方加速。在此，我们展示了如何将经典与量子算法同时实现二次加速，并保持两者间的四次方差距——即改进后的经典算法比原经典算法快二次方，而量子算法比原经典算法快八次方。我们还进一步改进了量子算法，使其相对于改进后的经典算法的加速比提升至六次方。目前仅证明了这些加速适用于检测任务而非恢复任务，但提出了强有力的合理性论证表明该算法同样能实现恢复功能。 补注：本文完成后，A. Schmidhuber提请我们注意参考文献3。该研究改进了特定随机算子谱范数的最佳现有界限。由于该算子的范数会影响运行时，此项改进使得我们无法再证明存在多项式加速。我们的结果基于该算子谱的特定性质（不仅涉及最大特征值，还包括态密度）。因此，若这些性质依然成立，加速效应仍将存在。为避免修改全文，我们保留原内容，仅在末尾新增一节讨论所需态密度性质，并分析该性质可能适用的场景（已有多个问题利用此类四次方量子加速技术，本文方法很可能适用于其中部分问题）。