量子核算机是否有望能破解 Lattice Problems 以及 LWE？尽管这一问题长期以来遭到重视，但鲜有实质性发展。

  近来，清华大学穿插信息研讨院助理教授陈一镭在 eprint 上发布的一篇论文，给出了破解格暗码的量子算法，引发了全球核算机范畴的震慑。

  清华大学在今日的官方公告中表明：「陈一镭的作业提出了一个全新的量子算法来处理 LWE 以及与之等价的格问题。这项作业仍在同行评议中。假如被验证为正确，将为这个悬而未决的问题给出必定的答复。」

  它在科学上的含义将是双层的：榜首，这将是自 30 年前 Peter Shor 提出大数分化的量子算法以来，最重要的量子算法打破。

  第二，这将对美国 NIST 曩昔 10 年来挑选后量子暗码规划的思路发生推翻性的影响，由于大都选出的后量子暗码计划都是根据 Lattice Problems 或 LWE。陈一镭的作业无疑将使他们安全性遭到质疑。

  这篇论文提出的算法及剖析极为新颖而艰深。回想 Wiles 1994 年处理费马大定理（Fermats Last Theorem），以及 Perelman 2002 年处理庞佳莱猜测（Poincaré Conjecture）后，都经过一年以上专家们方能完全认证其正确性。陈一镭的作业，意料也需求数月时刻才干完结验证认可。咱们静候科学界对此作业的后续反响。

  对此，图灵奖取得者、量子核算范畴威望、清华穿插信息研讨院院长姚期智给出高度评价：「作为一个青年教师，陈一镭能勇于应战如格暗码这样的世界级科学难题，令人赞佩！」

  从论文称谢部分的内容来看，为理论核算机范畴引进格暗码和容错学习问题的纽约大学核算机科学家、2018 年哥德尔奖得主 Oded Regev 自己应该现已看过论文手稿。

  具体而言，这篇论文展现了一种多项式时刻量子算法，用于求解具有特定多项式模数 - 噪声比的有误学习问题（LWE）。结合 Regev [J.ACM 2009] 所展现的从格问题到 LWE 的复原，论文得到了多项式时刻量子算法，用于求解一切 n 维网格的决定性最短向量问题（GapSVP）和最短独立向量问题（SIVP），其近似因子为

  。在此之前，还没有一点多项式乃至亚指数时刻的量子算法能够在任何多项式近似因子内求解一切格的 GapSVP 或 SIVP。

  首要，陈一镭在量子算法的规划中引进了具有杂乱方差的高斯函数，特别是运用了复高斯函数离散傅里叶变换中的卡斯特波特征。其次，陈一镭运用带有复高斯窗口的窗口量子傅里叶变换，这使得能够结合时域和频域的信息。运用这些技能，陈一镭将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 隐秘和差错项的经典线性方程，终究运用高斯消元法求解线性方程组。

  3.1 节展现了具有几个已知隐秘坐标的 LWE 和规范 LWE 相同难；

  3.2 介绍了将 LWE 转换成具有仅有最短向量的特别 q-ary 格；

  3.5 节具体供给了首要量子算法的九个过程，但将一切长度超越三页的证明推迟到第 3.6 节；

  论文展现了 LWE 的三种变体，终究一个变体在 Def. 3.4 中正式界说，本文提出的量子算法终究将处理这一个问题。

  下面三种减缩都是对现有经典多项式时刻减缩的细小修正，从规范 LWE 到它们的变体。

  现在界说一个 q-ary 格，使得找到这个特别 q-ary 格的仅有最短向量意味着求解

  本节中，作者运转一个由 9 大过程组成的量子子程序，时刻杂乱度为 O (n) 次。每次运转量子子程序时都会取得一个经典线性方程，其间随机系数在

  中的最短向量上（与 LWE 隐秘和差错向量相关）。因而，运转 O (n) 次后将得到一个满秩线性方程组，并经过高斯消元法核算 LWE 隐秘项和差错项。

  如下为量子子程序中 9 大过程的高档描绘，包含了每个过程中取得的状况和经典信息。

  过程 5：将 φ_4⟩ 区分为了高阶和低阶 h′⟩ h′′⟩，然后丈量 h′′⟩。为了推导出 φ_5⟩的表达式，作者注意到 φ_4⟩ 能够等效地写为：

  在第 8 步中，作者首要履行四次操作，接着进行部分丈量，终究将这四次操作回转（将保证这四次操作是可逆的）。方针是提取 v′_1 mod D^2_p1，终究返回到 φ_7⟩。也就是说，将学习 v′_1 mod D^2_p1 而不折叠或修正 φ_7⟩。

  过程 9：从 v′_1 mod D^2_p1 和 φ_8⟩ 中提取隐秘上的线 步中，作者的方针是将 φ_8⟩ 转换为隐秘上的经典线性方程，终究给出如下主引理（引理 3.8）的证明。过程 9 运用过程 8 中取得的 v′_1 mod D^2_p1 信息，并刺进 LWE 隐秘中的已知项的 κ-1 坐标。

  陈一镭是清华大学穿插信息学院助理教授，上海期智研讨院 PI。曾任 VISA 研讨院研讨员。于 2018 年取得波士顿大学核算机博士学位，本科毕业于上海交通大学。首要研讨爱好是暗码学，特别是在伪随机，格暗码，数论，和量子核算等方向。

  在 2022 年这篇研讨中，陈一镭团队和普林斯顿大学的刘启鹏和 Mark Zhandry 提出了一个能处理特别格问题的多项式时刻量子算法。这些特别格问题是 SIS 和 LWE 的变种。他们尽管并不等价于规范的格问题，可是现已很接近于暗码学常用的问题。他们的量子算法中运用了一种被称为 “过滤” 的办法，是在量子算法的规划中榜首次运用，可能为未来量子算法的规划带来新的思路。