“JVG算法”仅在极小数字上获胜

Source: Hacker News

抱歉打断您关于 AI 末日等常规话题的阅读，回到本博客最早期的传统内容……但我已经收到了多条信息，要求我评论一种叫做 “JVG（Jesse–Victor–Gharabaghi）算法” 的东西（是的，作者把它以自己的名字命名）。该算法被宣传为对 Shor 因式分解算法的巨大改进，据称（根据流行文章）只需要 5,000 物理量子位就能破解 RSA‑2048。

为什么 JVG 算法行不通

仔细检查后可以发现，论文的核心新想法是：在 Shor 算法的关键步骤——对所有 (r) 进行叠加并计算 (x^r \bmod N)——中，作者改为先在经典计算机上预先计算所有 (x^r \bmod N)，然后把它们全部加载到量子态中。

(r) 的取值数量是指数级的。把它们全部算出来需要指数时间，而把它们加载进量子计算机同样也需要指数时间。我们从 (n^2) 时间的“锅”跳到了 (2^n) 时间的“火”。这只能在极小的数字上看起来有点优势；在大数上则毫无希望。

如果想看到更礼貌、更详细的解释，请参阅这篇 Hacker News 讨论或这篇 Postquantum.com 文章。

可疑主张的警示信号

• 这篇论文没有出现在 arXiv 上，而是发布在一个叫 “Preprints.org” 的站点上。我应该把它加入我著名的《判断数学突破是否错误的十个迹象》列表中。虽然 arXiv 也会收录质量不高的工作，但大多数真正的突破都会出现在 arXiv，或是像 ECCC 或 IACR ePrint archive 这样的权威渠道。

• 简单的Google 搜索会发现该主张被点击诱饵、链接农场式的新闻站点大肆宣传，却被正规科学媒体忽视——是的，连平时的量子炒作机器也没有碰到这个。

通常，当某件事如此糟糕时，最仁慈的做法是让它在默默无闻中消亡。然而，在这种情况下，作者的智力流氓行为以及对真相的彻底漠视已经足以让他们永远背上一点小小的“鸡蛋”。