The “JVG algorithm” only wins on tiny numbers
Quantum computing's latest 'breakthrough,' the 'JVG algorithm,' receives a blistering debunking from Scott Aaronson, who labels its authors 'intellectual hooligans.' The story resonated on HN for Aaronson's characteristic no-holds-barred takedown and the deeper discussion it sparked about the pervasive hype in quantum computing. The community debated the etiquette of self-naming algorithms and the overall state of quantum progress.
The Lowdown
Scott Aaronson takes aim at the recently publicized 'JVG algorithm,' which claimed to significantly improve Shor's factoring algorithm and enable RSA-2048 cracking with minimal qubits. Aaronson meticulously exposes the fundamental flaw: the JVG algorithm's core 'innovation' relies on classically precomputing exponentially many values, then loading them into a quantum state, effectively moving the exponential complexity from the quantum part to the classical precomputation.
- The JVG algorithm proposed to break RSA-2048 with only 5,000 physical qubits, claiming a vast improvement over Shor's algorithm.
- Aaronson explains that the supposed 'speedup' originates from replacing a quantum computation with classical precomputation of xr mod N for all r.
- This classical precomputation and subsequent loading into the quantum computer requires exponential time, rendering the algorithm useless for large numbers.
- Aaronson highlights critical red flags: the paper's publication on 'Preprints.org' (not a reputable arXiv alternative) and its amplification by clickbait sites while being ignored by established science outlets.
- He concludes with a scathing critique of the authors' 'intellectual hooliganism' and 'total lack of concern for what’s true.'
This takedown serves as a stark reminder that even seemingly groundbreaking claims in complex fields like quantum computing require rigorous scrutiny to differentiate genuine progress from academic opportunism and hype.
The Gossip
Self-Naming Scrutiny
Commenters debated the appropriateness of the JVG authors naming the algorithm after themselves. While some pointed out precedents like AVL trees and RSA (which were named *after* their inventors by others, not by the inventors themselves), others found it a 'gaudy' and presumptuous move, especially for a flawed paper. The discussion touched on John Carlos Baez's 'crackpot index' point about self-naming research.
Hype vs. Hardware
The discussion often veered into the broader state of quantum computing. Many expressed skepticism about the field's current practical achievements, noting that despite continuous hype, quantum computers have yet to factor anything non-trivial without classical assistance or prior knowledge. Some commenters contrasted QC hype with AI's more tangible progress and questioned Scott Aaronson's own history of 'quantum supremacy' claims. The general consensus leaned towards QC still being in very early, theoretical stages, far from practical applications.
Aaronson's Acidic Appraisal
A few comments directly addressed Scott Aaronson's sharp, unapologetic tone in debunking the JVG algorithm. One user highlighted the change in the blog post's title from a charitable description to a direct 'lambasting' and 'shaming,' acknowledging Aaronson's strong stance against 'intellectual hooliganism.' This also led to some questioning Aaronson's own past claims regarding quantum supremacy.