30 年来最重要的量子算法突破？
在计算机领域，办理格上的近似最短向量成绩（Approximate Shortest Vector Problems in Lattices。Lattice Problems）以及与之等价的容错学习成绩（Learning with Errors，LWE）是典范的算法难题，科学界普遍认为它们超出了传统计算机的能力范围。
量子计算机是否有望能破解 Lattice Problems 以及 LWE？虽然这一成绩长期以来受到关注，但鲜有实质性进展。
近日，清华大学交叉信息研究院助理教授陈一镭在 eprint 上发布的一篇论文，给出了破解格暗码的量子算法，引发了全球计算机领域的震撼。
论文地址：https://eprint.iacr.org/2024/555.pdf
论文标题：Quantum Algorithms for Lattice Problems
清华大学在今天的官方公告中表示：「陈一镭的工作提出了一个全新的量子算法来办理 LWE 以及与之等价的格成绩。这项工作仍在同行评议中。如果被验证为正确，将为这个悬而未决的成绩给出肯定的答复。」
它在科学上的意义将是双层的：第一，这将是自 30 年前 Peter Shor 提出大数分解的量子算法以来，最重要的量子算法突破。
第二，这将对美国 NIST 过去 10 年来选择后量子暗码设计的思路产生颠覆性的影响，因为多数选出的后量子暗码方案都是基于 Lattice Problems 或 LWE。陈一镭的工作无疑将使他们安全性受到质疑。
这篇论文提出的算法及分析极为新颖而深奥。回想 Wiles 1994 年办理费马大定理（Fermat's Last Theorem），以及 Perelman 2002 年办理庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
对此，图灵奖得主、量子计算领域权威、清华交叉信息研究院院长姚期智给出高度评价：「作为一个青年教师，陈一镭能勇于挑战如格暗码这样的世界级科学难题，令人赞佩！」
从论文致谢部分的内容来看，为理论计算机领域引入格暗码和容错学习成绩的纽约大学计算机科学家、2018 年哥德尔奖得主 Oded Regev 本人应该已经看过论文手稿。
那么，这篇论文究竟取得了怎样的突破？
具体而言，这篇论文展示了一种多项式时间量子算法，用于求解具有特定多项式模数 – 噪声比的有误学习成绩（LWE）。结合 Regev [J.ACM 2009] 所展示的从格成绩到 LWE 的还原，论文得到了多项式时间量子算法，用于求解所有 n 维网格的决定性最短向量成绩（GapSVP）和最短独立向量成绩（SIVP），其近似因子为
。在此之前，还没有任何多项式甚至亚指数时间的量子算法可以在任何多项式近似因子内求解所有格的 GapSVP 或 SIVP。
为了开发求解 LWE 的量子算法，这篇论文首要引入了两种新技术：
首先，陈一镭在量子算法的设计中引入了具有复杂方差的高斯函数，特别是利用了复高斯函数离散傅里叶变换中的卡斯特波特征。其次，陈一镭应用带有复高斯窗口的窗口量子傅里叶变换，这使得能够结合时域和频域的信息。利用这些技术，陈一镭将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 诡秘和缺点项的典范线性方程，最后利用高斯消元法求解线性方程组。
求解 LWE 的量子算法
论文第三章首要专注于定理的注明：
3.1 节展示了具有几个已知诡秘坐标的 LWE 和标准 LWE 一样难；
3.2 介绍了将 LWE 转换成具有唯一最短向量的特殊 q-ary 格；
3.3 节列出了首要量子算法中应用的参数；
3.4 节概述了首要的量子算法；
3.5 节详细提供了首要量子算法的九个方法，但将所有长度超过三页的注明推迟到第 3.6 节；
3.6 节提供了第 3.5 节中遗漏的所有详细注明。
具体而言：
论文展示了 LWE 的三种变体，最后一个变体在 Def. 3.4 中正式定义，本文提出的量子算法最终将办理这个成绩。
下面三种缩减都是对现有典范多项式时间缩减的微小修改，从标准 LWE 到它们的变体。
1. 有 k 个无缺点坐标的 LWE。
2. 有 k 个选择缺点项的 LWE。
3.LWE，诡秘遵循缺点分布。
将 LWE 转换成具有唯一最短向量的特殊 q-ary 格
现在定义一个 q-ary 格，使得找到这个特殊 q-ary 格的唯一最短向量意味着求解
。
设：
参数选择
本小节将介绍更多量子算法中应用的参数。设 D ∈ N + 为缩放参数。
参数是在以下约束下设置的（ 
）：
量子算法有九个方法，下面的每个条件通常只在一个或几个方法中应用：
首要量子算法的详细概述
本节中，作者运行一个由 9 大方法组成的量子子程序，时间复杂度为 O (n) 次。每次运行量子子程序时都会获得一个典范线性方程，其中随机系数在
中的最短向量上（与 LWE 诡秘和缺点向量相关）。因此，运行 O (n) 次后将得到一个满秩线性方程组，并通过高斯消元法计算 LWE 诡秘项和缺点项。
如下为量子子程序中 9 大方法的高级描述，包括了每个方法中获得的状态以及典范信息。
首要量子子程序：9 大方法详解
方法 1：在
上准备一个叠加，并应用复高斯窗。
方法 2：在 |φ1〉上应用
。
方法 3：在 |φ_2〉上 应用复高斯窗，得到 |φ_3〉 和 z′。
方法 4：在 |φ_3〉上应用
。
方法 5：将 |φ_4〉 划分为了高阶和低阶 |h′〉 |h′′〉，然后测量 |h′′〉。为了推导出 |φ_5〉的表达式，作者注意到 |φ_4〉 可以等效地写为：
方法 6：在 |φ_5〉应用
。
方法 7：提炼 |φ_6〉 的中心，得到纯虚高斯态 |φ_7〉。
方法 8：提炼 v′_1 mod D^2_p1 并保留 |φ_8〉 = |φ_7〉。
在第 8 步中，作者首先执行四次操作，然后进行部分测量，最后将这四次操作反转（将确保这四次操作是可逆的）。目标是提炼 v′_1 mod D^2_p1，最终返回到 |φ_7〉。也就是说，将学习 v′_1 mod D^2_p1 而不折叠或修改 |φ_7〉。
方法 9：从 v′_1 mod D^2_p1 和 |φ_8〉 中提炼诡秘上的线性方程。
在第 9 步中，作者的目标是将 |φ_8〉 转换为诡秘上的典范线性方程，最终给出如下主引理（引理 3.8）的注明。方法 9 应用方法 8 中获得的 v′_1 mod D^2_p1 信息，并插入 LWE 诡秘中的已知项的 κ-1 坐标。
陈一镭简介
陈一镭是清华大学交叉信息学院助理教授，上海期智研究院 PI。曾任 VISA 研究院研究员。于 2018 年获得波士顿大学计算机博士学位，本科毕业于上海交通大学。首要研究兴趣是暗码学，特别是在伪随机，格暗码，数论，和量子计算等方向。
在个人介绍中，陈一镭的研究成果首要包括设计了格成绩的量子算法，建立了多线性映射和代码混淆在格成绩上安全实现的基础，提出了注明 Fiat-Shamir 假设的方法，以及提出了一个不可逆群的构造。
也就是说，在 2022 年，陈一镭就发表了有关格成绩的研究。该研究「Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering」发表于 2022 年欧洲暗码大会（Eurocrypt 2022），并收到 Journal of Cryptology 邀稿。
在 2022 年这篇研究中，陈一镭团队和普林斯顿大学的刘启鹏和 Mark Zhandry 提出了一个能办理特殊格成绩的多项式时间量子算法。这些特殊格成绩是 SIS 和 LWE 的变种。他们虽然并不等价于标准的格成绩，但是已经非常接近于暗码学常用的成绩。他们的量子算法中应用了一种被称为 “过滤” 的方法，是在量子算法的设计中第一次应用，可能为未来量子算法的设计带来新的思路。
参考：
https://sqz.ac.cn/password-50