前段时间，由清华叉院助理教授陈一镭提出的全新「破解格密码的量子算法」，一经发表便引发了业内轰动。然而就在最近，关键的第 9 步被发现有无法修复的 bug，导致算法无法成立。

　　一直以来，解决格上的近似最短向量问题（Lattice Problems）以及带错误学习问题（LWE），都是计算机领域的经典算法难题k7注册下载安装。

　　尤其是在科学界看来，它们远远超出了传统计算机的能力范围。那么，量子计算机有望能破解 Lattice Problems 以及 LWE 吗？

　　前段时间，来自清华大学交叉信息研究院陈一镭助理教授，便针对这些问题提出了一种全新的「破解格密码的量子算法」k7注册下载安装。

　　如著名密码学家 N. P. Smart，就在第一时间发了篇博客文章，详细讨论了论文所带来的影响。

　　具体来说k7注册下载安装，陈教授提出的这种多项式时间量子算法，主要用于求解具有特定多项式模数-噪声比的「带错误学习问题」（LWE）。

　　通过结合 Regev 所提出的从网格问题到 LWE 的还原，便可以获得多项式时间量子算法，并可以在

　　的近似因子内求解所有 n 维网格的决策最短向量问题（GapSVP）和最短独立向量问题（SIVP）。

　　在此之前，还没有已知的多项式甚至亚指数时间量子算法可以在任何多项式近似因子内求解所有网格的 GapSVP 或 SIVP。

　　首先，在量子算法的设计中引入具有复杂方差的高斯函数。特别是，利用复高斯函数离散傅里叶变换中的卡斯特波特征。

　　其次，使用带有复高斯窗口的窗口量子傅里叶变换，从而能够结合时域和频域的信息。

　　基于此k7注册下载安装，便可以先将 LWE 实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为 LWE 秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组基本周期k7注册下载安装。

　　但遗憾的是，Hongxun Wu（UC 伯克利博二学生）和 Thomas Vidick（量子领域专家）发现，算法的第 9 步实际上存在一个尚不能修复的 bug轨窗帘。

　　也就是说，这个通过多项式模数-噪声比，来求解 LWE 的多项式时间量子算法，无法成立了。

　　对此作者表示，希望像复高斯（Complex Gaussian）和窗口 QFT（windowed QFT）这样的想法，会在量子计算中找到其他应用，而 LWE 问题或许会将有别的解决方法脉冲上升时间。

　　首先进行参数的设置，之后需要运行一个由九个步骤组成的量子子程序，共运行 O (n) 次啮合线。

　　论文中最关键的，是一个需要调用 O (n) 次的，由九个步骤组成的量子子程序。

　　在调用完 O (n) 次之后，便可以得到一个全秩线性方程组，并通过高斯消元法计算出 LWE 秘密和错误项。

　　步骤 5：将 φ4⟩分割成高阶 h′⟩和低阶 h′′⟩吹膜机三波，然后对 h′′⟩进行测量

　　在步骤 8 中，作者首先进行四次运算（可逆），然后进行部分测量，最后将四次运算反转。也就是说单环机构子程序，需要在不折叠或修改 φ7⟩的情况下，学习

　　步骤 9：从和 φ8⟩中提取秘密的线⟩转换为秘密的经典线性方程，并最终得到主 Lemma（3.8）的证明。

　　8.g⟩的写法，它只包含 p1...pκ 向量。因此 φ8.g⟩的表达式是错误的静联接。

　　平台声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。