The “JVG algorithm” only wins on tiny numbers

Source: Hacker News

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.

Why the JVG algorithm doesn’t work

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.

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.

Red flags for a dubious claim

• The paper didn’t appear on the arXiv, but on a site called “Preprints.org.” I should add this to my famous Ten Signs a Claimed Mathematical Breakthrough is Wrong. While the arXiv also hosts low‑quality work, most genuine breakthroughs appear there, or on reputable venues such as the ECCC or the IACR ePrint archive.

• A quick Google search shows the claim being amplified on click‑bait, link‑farming news sites, but ignored by reputable science outlets—yes, even the usual quantum hype‑machines weren’t touching this one!

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 sufficient to merit a permanent, tiny bit of egg on the authors’ faces.