The ”JVG algorithm” is crap
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 xr mod N in a superposition over all r’s, you instead precompute the xr mod N’s on a classical computer and then load them all into the quantum state.
Alright kids, why does this not work? Shall we call on someone in the back of the class—like, any undergrad quantum computing class in the world? Yes class, that’s right! 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 n2-time frying pan but into the 2n-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 from Hacker News or this from Postquantum.com.
Even for those who know nothing about quantum algorithms, is there anything that could’ve raised suspicion here?
- The paper didn’t appear on the arXiv, but someplace called “Preprints.org.” Come to think of it, I should add this to my famous Ten Signs a Claimed Mathematical Breakthrough is Wrong! It’s not that there isn’t tons of crap on the arXiv as well, but so far I’ve seen pretty much only crap on preprint repositories other than arXiv, ECCC, and IACR.
- Judging from a Google search, the claim seems to have gotten endlessly amplified on clickbait link-farming news sites, but ignored by reputable science news outlets—yes, even the usual quantum hypesters weren’t touching this one!
Often, when something is this bad, the merciful answer is to let it die in obscurity. In this case, I feel like there was a sufficient level of intellectual hooliganism, just total lack of concern for what’s true, that those involved deserve to have this Shtetl-Optimized post as a tiny bit of egg on their faces forever.
Follow
Comment #1 March 7th, 2026 at 10:07 pm
Concerning preprint repositories: the arXiv recently changed its policy to require that all papers have a primary version written in English, and among the pure math community I’ve seen some pushback and people looking into other alternatives. The main credible alternative for pure math is HAL, which contains plenty of non-crap papers as all French academics are required to post their work on it!
I’m not taking a position here on what anyone should do (and personally I expect I’ll keep using and supporting the arXiv), just pointing out that it’s plausible that in the near future a legitimate mathematical breakthrough might appear as a preprint somewhere other than arXiv.
Comment #2 March 8th, 2026 at 3:35 am
Isn’t “Hide the actual work of solving a problem in a pre-computation step” a very well-known and much mocked way of lying about how fast your algorithm is?
Comment #3 March 8th, 2026 at 8:14 am
Doug S. #2: Yes. In this case, if it worked to trade quantum computation for classical precomputation, that could indeed be a huge win. But it doesn’t work, or certainly not this way. For a version of the precomputation idea that does work (and that in fact, lets you parallelize the quantum part of Shor’s algorithm to run in logarithmic depth), see Cleve and Watrous 2000.
Comment #4 March 8th, 2026 at 1:51 pm
“JVG” isn’t even the right way to make that kind of acronym…if they’re all the authors on the same people, it should be in alphabetical order!
Comment #5 March 8th, 2026 at 2:14 pm
Scott #3: An even more similar type precomputation that actually works is “windowing”, where a series of controlled operations is done in blocks by using table lookups. For example, doing w controlled offsets into an n-qubit register costs ~2wn Toffolis but doing a w-qubit lookup of a 2^w value classical table and then an unconditional addition costs ~2^w + n Toffolis (and O(n2^w) classical computation).
Of course, those 2^w terms prevent large w’s from being used. Certainly you’d never set w to 2048! But setting w to 4 is obviously beneficial due to quantum gates being so much more expensive than classical gates. And the more expensive the operation being windowed, the larger the optimal value of w tends to be. For example, https://arxiv.org/abs/2306.08585 hits optimal at w=16 which is quite high.
Incidentally, I also had to field questions about this obviously bad JVG paper. Glad to have something to forward people to. Another red flag I was noting is that they do curve fits at tiny sizes, which is a common element of bad factoring papers.
Comment #6 March 9th, 2026 at 2:06 am
When i read the title, i thought they finally made quantum videotape (ask your parents, kids).
Glad to see their idea is nearly as practical.
Comment #7 March 9th, 2026 at 7:53 am
The authors naming the algorithm after themselves may also be an item to add to your Top Ten (now more than ten) signs that a math breakthrough is wrong.