看起来 “JVG algorithm” 只在极小的数字上获胜

Source: Hacker News

引言

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

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

为什么 JVG 算法行不通

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

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

表明该声明可疑的迹象

• 非 arXiv 发表渠道——该论文出现在 “Preprints.org” 而不是 arXiv、ECCC 或 IACR。我已把它加入我著名的《十个标志表明声称的数学突破是错误的》。虽然 arXiv 也会收录质量低劣的工作，但绝大多数可信的突破都会出现在那里或其他列出的仓库中。
• 标题党式的放大——一次快速的Google 搜索就能看到该声明在低质量、标题党新闻站点上被不断放大，而权威科学媒体（甚至通常的量子炒作网站）都对其置之不理。

通常，当某件事如此糟糕时，最仁慈的做法是让它在默默无闻中消失。但在本例中，肆意的学术流氓行为以及对真相的完全漠视，似乎值得留下永久的公开记录，以警示后人。

进一步阅读

• 原始预印本：“JVG（Jesse–Victor–Gharabaghi）算法” – Preprints.org
• 声称量子末日的流行文章 – BriefGlance
• Hacker News 讨论 – link
• Postquantum.com 分析 – link
• 十个标志表明声称的数学突破是错误的 – Scott Aaronson 博客