{"id":9615,"date":"2026-03-07T21:06:05","date_gmt":"2026-03-08T03:06:05","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=9615"},"modified":"2026-03-07T21:06:05","modified_gmt":"2026-03-08T03:06:05","slug":"the-jvg-algorithm-is-crap","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=9615","title":{"rendered":"The \u201dJVG algorithm\u201d is crap"},"content":{"rendered":"\n

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\u2013Victor\u2013Gharabaghi) algorithm”<\/a> (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<\/a>) allow RSA-2048 to be broken using only 5,000 physical qubits.<\/p>\n\n\n\n

On inspection, the paper’s big new idea is that, in the key step of Shor’s algorithm where you compute xr<\/sup> mod N in a superposition over all r’s, you instead precompute the xr<\/sup> mod N’s on a classical computer and then load them all into the quantum state.<\/p>\n\n\n\n

Alright kids, why does this not work? Shall we call on someone in the back of the class—like, any<\/em> undergrad quantum computing class in the world? Yes class, that’s right! There are exponentially many r’s.<\/em> Computing them all takes exponential time, and loading them into the quantum computer also<\/em> takes exponential time. We’re out of the n2<\/sup>-time frying pan but into the 2n<\/sup>-time fire. This can only look like it wins on tiny numbers; on large numbers it’s hopeless.<\/p>\n\n\n\n

If you want to see people explaining the same point more politely and at greater length, try this from Hacker News<\/a> or this from Postquantum.com<\/a>.<\/p>\n\n\n\n

Even for those who know nothing about quantum algorithms, is there anything that could’ve raised suspicion here?<\/p>\n\n\n\n

    \n
  1. 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<\/a>! It’s not that there isn’t tons of crap on the arXiv as well, but so far I’ve seen pretty much only<\/em> crap on preprint repositories other than arXiv<\/a>, ECCC<\/a>, and IACR<\/a>.<\/li>\n\n\n\n
  2. Judging from a Google search<\/a>, 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!<\/li>\n<\/ol>\n\n\n\n

    Often, when something is this<\/em> 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<\/em> post as a tiny bit of egg on their faces forever.<\/p>\n","protected":false},"excerpt":{"rendered":"

    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\u2013Victor\u2013Gharabaghi) algorithm” (yes, the authors named it after themselves). This is presented as a massive improvement […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,4,16,17],"tags":[],"class_list":["post-9615","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum","category-rage-against-doofosity","category-speaking-truth-to-parallelism"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/9615","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=9615"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/9615\/revisions"}],"predecessor-version":[{"id":9620,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/9615\/revisions\/9620"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=9615"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=9615"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=9615"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}