It looks like the “JVG algorithm” only wins on tiny numbers

Source: Hacker News

Introduction

Sorry to interrupt your regular programming about the AI apocalypse, etc., and return to the traditional beat of this blog’s very earliest years … but I’ve now gotten multiple messages asking me to comment on something called the “JVG (Jesse–Victor–Gharabaghi) algorithm” (yes, the authors named it after themselves). This is presented as a massive improvement over Shor’s factoring algorithm, which could (according to popular articles) allow RSA‑2048 to be broken using only 5,000 physical qubits.

On inspection, the paper’s big new idea is that, in the key step of Shor’s algorithm where you compute (x^r \bmod N) in a superposition over all (r)’s, you instead pre‑compute the (x^r \bmod N)’s on a classical computer and then load them all into the quantum state.

Why the JVG algorithm doesn’t work

There are exponentially many (r)’s. Computing them all takes exponential time, and loading them into the quantum computer also takes exponential time. We’re out of the (n^2)-time frying pan but into the (2^n)-time fire. This can only look like it wins on tiny numbers; on large numbers it’s hopeless.

If you want to see people explaining the same point more politely and at greater length, try this discussion on Hacker News or this article on Postquantum.com.

Signs that the claim is dubious

• Non‑arXiv venue – The paper appeared on “Preprints.org” rather than on the arXiv, ECCC, or IACR. I’ve added this to my famous Ten Signs a Claimed Mathematical Breakthrough is Wrong. While the arXiv also hosts low‑quality work, the overwhelming majority of credible breakthroughs appear there or in the other listed repositories.
• Click‑bait amplification – A quick Google search shows the claim being endlessly amplified on low‑quality, click‑bait news sites, while reputable science outlets (and even the usual quantum hype‑sites) have ignored it.

Often, when something is this bad, the merciful answer is to let it die in obscurity. In this case, however, the level of intellectual hooliganism and total lack of concern for truth seem to merit a permanent, public record of the mistake.

Further reading

• Original preprint: “JVG (Jesse–Victor–Gharabaghi) algorithm” – Preprints.org
• Popular article claiming a quantum apocalypse – BriefGlance
• Hacker News discussion – link
• Postquantum.com analysis – link
• Ten Signs a Claimed Mathematical Breakthrough is Wrong – Scott Aaronson blog