{"id":6957,"date":"2023-01-04T23:06:20","date_gmt":"2023-01-05T05:06:20","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=6957"},"modified":"2023-01-05T09:05:29","modified_gmt":"2023-01-05T15:05:29","slug":"cargo-cult-quantum-factoring","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=6957","title":{"rendered":"Cargo Cult Quantum Factoring"},"content":{"rendered":"\n

Just days after we celebrated my wife’s 40th birthday<\/a>, she came down with COVID, meaning she’s been isolating and I’ve been spending almost all my time dealing with our kids.<\/p>\n\n\n\n

But if experience has taught me anything, it’s that the quantum hype train never slows down. In the past 24 hours, at least four people have emailed to ask me about a new paper<\/a> entitled “Factoring integers with sublinear resources on a superconducting quantum processor.” Even the security expert Bruce Schneier, while skeptical, took the paper surprisingly seriously<\/a>.<\/p>\n\n\n\n

The paper claims … well, it’s hard to pin down what it claims, but it’s certainly given many people the impression<\/em> that there’s been a decisive advance on how to factor huge integers, and thereby break the RSA cryptosystem, using a near-term quantum computer. Not<\/em> by using Shor’s Algorithm<\/a>, mind you, but by using the deceptively similarly named Schnorr’s Algorithm<\/a>. The latter is a classical algorithm based on lattices, which the authors then “enhance” using the heuristic quantum optimization method called QAOA<\/a>.<\/p>\n\n\n\n

For those who don’t care to read further, here is my 3-word review:<\/p>\n\n\n\n

No. Just No.<\/h2>\n\n\n\n

And here’s my slightly longer review:<\/p>\n\n\n\n

Schnorr \u2260 Shor<\/em>. Yes, even when Schnorr’s algorithm is dubiously \u201cenhanced\u201d using QAOA—a quantum algorithm that, incredibly, for all the hundreds of papers written about it, has not yet been convincingly argued to yield any speedup for any problem whatsoever (besides, as it were, the problem of reproducing its own pattern of errors<\/a>) (one possible recent exception<\/a> from Sami Boulebnane and Ashley Montanaro).<\/p>\n\n\n\n

In the new paper, the authors spend page after page saying-without-saying that it might<\/em> soon become possible to break RSA-2048, using a NISQ (i.e., non-fault-tolerant) quantum computer. They do so via two time-tested strategems:<\/p>\n\n\n\n

    \n
  1. the detailed exploration of irrelevancies (mostly, optimization of the number of qubits<\/em>, while ignoring the number of gates<\/em>), and<\/li>\n\n\n\n
  2. complete silence about the one crucial point<\/strong>.<\/li>\n<\/ol>\n\n\n\n

    Then, finally, they come clean about the one crucial point in a single sentence of the Conclusion section:<\/p>\n\n\n\n

    \n

    It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.<\/p>\n<\/blockquote>\n\n\n\n

    \u201cUnclear\u201d is an understatement here. It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr’s algorithm on your laptop. And if the latter were able to break RSA, it would’ve already done so.<\/p>\n\n\n\n

    All told, this is one of the most actively misleading quantum computing papers I\u2019ve seen in 25 years, and I\u2019ve seen … many. Having said that, this actually isn’t<\/em> the first time I’ve encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor\u2019s algorithm, should somehow \u201crub off\u201d onto quantum optimization heuristics that embody none of the actual insights of Shor’s algorithm, as if by sympathetic magic. Since this idea needs a name, I’d hereby like to propose Cargo Cult Quantum Factoring<\/strong>.<\/p>\n\n\n\n

    And with that, I feel I’ve adequately discharged my duties here to sanity and truth. If I’m slow to answer comments, it’ll be because I’m dealing with two screaming kids.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Just days after we celebrated my wife’s 40th birthday, she came down with COVID, meaning she’s been isolating and I’ve been spending almost all my time dealing with our kids. But if experience has taught me anything, it’s that the quantum hype train never slows down. In the past 24 hours, at least four people […]<\/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_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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},"categories":[5,4,16,17],"tags":[],"class_list":["post-6957","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_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6957","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=6957"}],"version-history":[{"count":7,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6957\/revisions"}],"predecessor-version":[{"id":6965,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6957\/revisions\/6965"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6957"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6957"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6957"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}