{"id":8834,"date":"2025-04-30T22:16:57","date_gmt":"2025-05-01T03:16:57","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=8834"},"modified":"2025-05-05T14:29:25","modified_gmt":"2025-05-05T19:29:25","slug":"quantum-ai-everything-but-trump","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=8834","title":{"rendered":"Quantum! AI! Everything but Trump!"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li>Grant Sanderson, of <a href=\"https:\/\/www.youtube.com\/c\/3blue1brown\">3blue1brown<\/a>, has put up a <a href=\"https:\/\/www.youtube.com\/watch?v=RQWpF2Gb-gU\">phenomenal YouTube video explaining Grover&#8217;s algorithm<\/a>, and dispelling the fundamental misconception about quantum computing, that QC works simply by &#8220;trying all the possibilities in parallel.&#8221; Let me not futz around: <strong>this video explains, in 36 minutes, what I&#8217;ve tried to explain over and over on this blog for 20 years &#8230; and it does it better.  It&#8217;s a masterpiece.<\/strong> Yes, I consulted with Grant for this video (he wanted my intuitions for &#8220;why is the answer \u221aN?&#8221;), and I even have a cameo at the end of it, but I wish I had <em>made<\/em> the video. Damn you, Grant!<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The incomparably great, and <em>absurdly<\/em> prolific, blogger <a href=\"https:\/\/thezvi.substack.com\/\">Zvi Mowshowitz<\/a> and yours truly <a href=\"https:\/\/www.youtube.com\/watch?v=NMwjqqtU5Dw\">spend 1 hour and 40 minutes<\/a> discussing AI existential risk, education, blogging, and more. I end up \u201cinterviewing\u201d Zvi, who does the majority of the talking, which is fine by me, as he has many important things to say! (Among them: his searing critique of those K-12 educators who see it as their life\u2019s mission to <em>prevent<\/em> kids from learning too much too fast\u2014I\u2019ve linked his best piece on this from the header of this blog.) Thanks so much to Rick Coyle for arranging this conversation.<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Progress in quantum complexity theory!<\/strong> In 2000, <a href=\"https:\/\/arxiv.org\/abs\/cs\/0009002\">John Watrous showed<\/a> that the Group Non-Membership problem is in the complexity class <a href=\"https:\/\/en.wikipedia.org\/wiki\/QMA\">QMA (Quantum Merlin-Arthur)<\/a>. In other words, if some element g is <em>not<\/em> contained in a given subgroup H of an exponentially large finite group G, which is specified via a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Black_box_group\">black box<\/a>, then there&#8217;s a short quantum proof that g\u2209H, with only ~log|G| qubits, which can be verified on a quantum computer in time polynomial in log|G|. This soon raised the question of whether Group Non-Membership could be used to separate QMA from QCMA by oracles, where <a href=\"https:\/\/complexityzoo.net\/Complexity_Zoo:Q#qcma\">QCMA (Quantum Classical Merlin Arthur)<\/a>, defined by <a href=\"https:\/\/arxiv.org\/abs\/quant-ph\/0210077\">Aharonov and Naveh<\/a> in 2002, is the subclass of QMA where the proof needs to be classical, but the verification procedure can still be quantum. In other words, could Group Non-Membership be the first non-quantum example where <em>quantum proofs actually help<\/em>?<br><br>In 2006, alas, <a href=\"https:\/\/arxiv.org\/abs\/quant-ph\/0604056\">Greg Kuperberg and I showed<\/a> that the answer was probably &#8220;no&#8221;: Group Non-Membership has &#8220;polynomial QCMA query complexity.&#8221; This means that there&#8217;s a QCMA protocol for the problem where Arthur makes only polylog|G| quantum queries to the group oracle&#8212;albeit, <em>possibly<\/em> an exponential in log|G| number of quantum computation steps besides that! To prove our result, Greg and I needed to make mild use of the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Classification_of_finite_simple_groups\">Classification of Finite Simple Groups<\/a>, one of the crowning achievements of 20th-century mathematics (its proof is about 15,000 pages long). We conjectured (but couldn&#8217;t prove) that someone else, who knew more about the Classification than we did, could show that Group Non-Membership was simply in QCMA outright.<br><br>Now, after almost 20 years, <a href=\"https:\/\/arxiv.org\/abs\/2504.05547\">Fran\u00e7ois Le Gall,&nbsp;Harumichi Nishimura,&nbsp;and Dhara Thakkar have finally proven our conjecture<\/a>&#8212;showing that Group Order, and therefore also Group Non-Membership, are indeed in QCMA. They did indeed need to use the Classification, doing one thing for almost all finite groups covered by the Classification, but a different thing for groups of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ree_group\">&#8220;Ree type&#8221;<\/a> (whatever those are).<br><br>Interestingly, the Group Membership problem had <em>also<\/em> been a candidate for separating <a href=\"https:\/\/complexityzoo.net\/Complexity_Zoo:B#bqpqpoly\">BQP\/qpoly<\/a>, or quantum polynomial time with polynomial-size quantum advice&#8212;my personal favorite complexity class&#8212;from <a href=\"https:\/\/complexityzoo.net\/Complexity_Zoo:B#bqppoly\">BQP\/poly<\/a>, or the same thing with polynomial-size <em>classical<\/em> advice.  And it might conceivably still be!  The authors explain to me that their protocol doesn&#8217;t put Group Membership (with group G and subgroup H depending only on the input length n) into BQP\/poly, the reason being that their short classical witnesses for g\u2209H depend on both g <em>and<\/em> H, in contrast to Watrous&#8217;s quantum witnesses which depended only on H.  So there&#8217;s still plenty that&#8217;s open here!  Actually, for that matter, I don&#8217;t know of good evidence that the entire Group Membership problem isn&#8217;t in BQP&#8212;i.e., that quantum computers can&#8217;t just <em>solve<\/em> the whole thing outright, with no Merlins or witnesses in sight!<br><br>Anyway, huge congratulations to Le Gall, Nishimura, and Thakkar for peeling back our ignorance of these matters a bit further!  Reeeeeeeee!<br><\/li>\n\n\n\n<li><strong>Potential big progress in quantum algorithms!<\/strong> <a href=\"https:\/\/arxiv.org\/abs\/2504.11049\">Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone (GLM) have given<\/a> what they present as a quantum algorithm to estimate the determinant of an n\u00d7n matrix A, exponentially faster in some contexts than we know how to do it classically.<br><br>[<strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-red-color\">Update (May 5):<\/mark><\/strong> In the comments, Alessandro Luongo <a href=\"https:\/\/arxiv.org\/abs\/2011.06475\">shares a paper<\/a> where he and Changpeng Shao describe what appears to be essentially the same algorithm back in 2020.]<br><br>The algorithm is closely related to the 2008 <a href=\"https:\/\/en.wikipedia.org\/wiki\/HHL_algorithm\">HHL (Harrow-Hassidim-Lloyd)<\/a> quantum algorithm for solving systems of linear equations. Which means that anyone who knows the history of this class of quantum algorithms knows to ask immediately: what&#8217;s the <a href=\"https:\/\/www.scottaaronson.com\/papers\/qml.pdf\">fine print<\/a>? A couple weeks ago, when I visited Harvard and MIT, I had a chance to catch up with Seth Lloyd, so I asked him, and he kindly told me. Firstly, we assume the matrix A is Hermitian and positive semidefinite. Next, we assume A is sparse, and not only that, but there&#8217;s a <a href=\"https:\/\/arxiv.org\/pdf\/2305.01178\">QRAM<\/a> data structure that points to its nonzero entries, so you don&#8217;t need to do Grover search or the like to find them, and can query them in coherent superposition. Finally, we assume that all the eigenvalues of A are at least some constant \u03bb>0. The algorithm then estimates det(A), to multiplicative error \u03b5, in time that scales linearly with log(n), and polynomially with 1\/\u03bb and 1\/\u03b5.<br><br>Now for the challenge I leave for ambitious readers: <strong>is there a classical randomized algorithm to estimate the determinant under the same assumptions and with comparable running time?<\/strong> In other words, can the GLM algorithm be <a href=\"https:\/\/scottaaronson.blog\/?p=3880\">&#8220;Ewinized&#8221;<\/a>? Seth didn&#8217;t know, and I think it&#8217;s a wonderful crisp open question! On the one hand, if Ewinization is possible, it <a href=\"https:\/\/scottaaronson.blog\/?p=2155\">wouldn&#8217;t be the first time<\/a> that publicity on this blog had led to the brutal murder of a tantalizing quantum speedup. On the other hand &#8230; well, maybe not! I also consider it possible that the problem solved by GLM&#8212;for exponentially-large, implicitly-specified matrices A&#8212;is <a href=\"https:\/\/arxiv.org\/abs\/quant-ph\/0606179\">BQP-complete<\/a>, as for example was the general problem solved by HHL. This would mean, for example, that one could embed Shor&#8217;s factoring algorithm into GLM, and that there&#8217;s no hope of dequantizing it unless P=BQP. (Even then, though, just like with the HHL algorithm, we&#8217;d still face the question of whether the GLM algorithm was &#8220;independently useful,&#8221; or whether it merely reproduced quantum speedups that were already known.)<br><br>Anyway, quantum algorithms research lives! So does dequantization research! If basic science in the US is able to continue at all&#8212;the thing I promised <em>not<\/em> to talk about in this post&#8212;we&#8217;ll have plenty to keep us busy over the next few years.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"","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_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_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":[31,5,12,4,8],"tags":[],"class_list":["post-8834","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-metaphysical-spouting","category-quantum","category-the-fate-of-humanity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8834","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=8834"}],"version-history":[{"count":11,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8834\/revisions"}],"predecessor-version":[{"id":8846,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8834\/revisions\/8846"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8834"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8834"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}