量子算法解决格问题
2024-04-12
本文提出了一种多项式时间量子算法，用于解决具有特定多项式模噪比的带误差学习问题 (LWE)。结合 Regev [J.ACM 2009] 提出的将格问题简化为 LWE 的方法，该算法可以解决所有 n 维格的决策最短向量问题 (GapSVP) 和最短独立向量问题 (SIVP)，逼近因子为 Ω~(n^4.5) 。此前，没有任何多项式时间或亚指数时间量子算法能够在任何多项式逼近因子内解决所有格的 GapSVP 或 SIVP。作者引入两个新技术来开发解决 LWE 的量子算法，包括在量子算法设计中引入具有复方差的高斯函数，以及使用具有复高斯窗的加窗量子傅里叶变换。然而，该算法在第 9 步存在错误，目前尚不清楚如何修复。
42