主要观点：展示了用于解决具有特定多项式模噪声比的误差学习问题（LWE）的多项式时间量子算法，结合 Regev 所展示的从格问题到 LWE 的归约，得到了求解所有(n)维格的判定最短向量问题（GapSVP）和最短独立向量问题（SIVP）的多项式时间量子算法，近似因子为(\tilde{\Omega}(n^{4.5}))，之前对于所有格在任何多项式近似因子内求解 GapSVP 或 SIVP 都没有多项式甚至亚指数时间的量子算法。
关键信息：

• 为开发求解 LWE 的量子算法，主要引入了两种新技术，包括在量子算法设计中引入具有复方差的高斯函数，利用复高斯函数离散傅里叶变换中的喀斯特波特征，以及使用具有复高斯窗口的加窗量子傅里叶变换。
• 通过这些技术，先将 LWE 实例转换为具有纯虚高斯振幅的量子态，再转换为关于 LWE 秘密和误差项的经典线性方程，最后使用高斯消元法求解线性方程组，从而得到求解 LWE 的多项式时间量子算法。
  重要细节：
• 4 月 18 日更新，算法的第 9 步存在一个未知如何修复的错误，详情见第 3.5.9 节（第 37 页），目前展示用于求解具有多项式模噪声比的 LWE 的多项式时间量子算法的主张不成立，但保留了论文的其余部分（在第 8 步中添加了一个操作的说明），希望像复高斯和加窗量子傅里叶变换这样的想法能在量子计算中找到其他应用或以其他方式处理 LWE。
• 作者为 Yilei Chen，发表于 Cryptology ePrint Archive，论文编号 2024/555，网址为 https://eprint.iacr.org/2024/555 。