{"id":1537,"date":"2013-09-20T16:02:49","date_gmt":"2013-09-20T21:02:49","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1537"},"modified":"2017-01-12T16:22:11","modified_gmt":"2017-01-12T21:22:11","slug":"the-unitarihedron-the-jewel-at-the-heart-of-quantum-computing","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1537","title":{"rendered":"The Unitarihedron: The Jewel at the Heart of Quantum Computing"},"content":{"rendered":"

Update (9\/24):<\/strong><\/span> This parody post was a little like a belch: I felt it build up in me as I read about the topic, I let it out, it was easy and amusing, I don’t feel any profound guilt over it—but on the other hand, not one of the crowning achievements of my career.\u00a0 As several commenters correctly pointed out, it may be true<\/em> that, mostly because of the name and other superficialities, and because of ill-founded speculations about “the death of locality and unitarity,” the amplituhedron work is currently inspiring a flood of cringe-inducing misstatements on the web.\u00a0 But, even if true, still the much more interesting questions are what’s actually going on, <\/em>and whether or not there are nontrivial connections to computational complexity.<\/p>\n

Here I have good news: if nothing else, my “belch” of a post at least attracted some knowledgeable commenters to contribute excellent questions and insights, which have increased my own understanding of the subject from\u00a0\u03b52<\/sup> to \u03b5.\u00a0 See especially this superb comment by David Speyer<\/a>—which, among other things, pointed me to a phenomenal quasi-textbook<\/a> on this subject by Elvang and Huang.\u00a0 My most immediate thoughts:<\/p>\n

    \n
  1. The “amplituhedron” is only the latest in a long line of research over the last decade—Witten, Turing biographer Andrew Hodges<\/a>, and many others have been important players—on how to compute scattering amplitudes more efficiently than by summing zillions of Feynman diagrams.\u00a0 One of the key ideas is to find combinatorial formulas that express complicated scattering amplitudes recursively in terms of simpler ones.<\/li>\n
  2. This subject seems to be begging<\/em> for a computational complexity perspective.\u00a0 When I read Elvang and Huang, I felt like they were working hard not<\/em> to say anything about complexity: discussing the gains in efficiency from the various techniques they consider in informal language, or in terms of concrete numbers of terms that need to be summed for 1 loop, 2 loops, etc., but never in terms of asymptotics.\u00a0 So if it hasn’t been done already, it looks like it could be a wonderful project for someone just to translate what’s already known<\/em> in this subject into complexity language.<\/li>\n
  3. On reading about all these “modern” approaches to scattering amplitudes, one of my first reactions was to feel slightly<\/em> less guilty about never having learned how to calculate Feynman diagrams!\u00a0 For, optimistically, it looks like some of that headache-inducing machinery (ghosts, off-shell particles, etc.) might be getting less relevant anyway—there being ways to calculate some of the same things that are not only more conceptually satisfying but also faster.<\/li>\n<\/ol>\n
    \n

    Many readers of this blog probably already saw Natalie Wolchover’s Quanta<\/em> article “A Jewel at the Heart of Quantum Physics,”<\/a> which discusses the “amplituhedron”: a mathematical structure that IAS physicist Nima Arkami-Hamed and his collaborators have recently been investigating.\u00a0 (See also here<\/a> for Slashdot commentary, here<\/a> for Lubos’s take, here<\/a> for Peter Woit’s, here<\/a> for a Physics StackExchange thread, here<\/a> for Q&A with Pacific Standard, and here<\/a> for an earlier but closely-related 154-page paper.)<\/p>\n

    At first glance, the amplituhedron appears to be a way to calculate scattering amplitudes, in the planar limit of a certain mathematically-interesting (but, so far, physically-unrealistic) supersymmetric quantum field theory, much more efficiently than by summing thousands of Feynman diagrams.\u00a0 In which case, you might say: “wow, this sounds like a genuinely-important advance for certain parts of mathematical physics!\u00a0 I’d love to understand it better.\u00a0 But, given the restricted class of theories it currently applies to, it does<\/em> seem a bit premature to declare this to be a ‘jewel’ that unlocks all of physics, or a death-knell for spacetime, locality, and unitarity, etc. etc.”<\/p>\n

    Yet you’d be wrong: it isn’t premature at all.\u00a0 If anything, the popular articles have understated<\/em> the revolutionary importance of the amplituhedron.\u00a0 And the reason I can tell you that with such certainty is that, for several years, my colleagues and I have been investigating a mathematical structure that contains the amplituhedron, yet is even richer and more remarkable.\u00a0 I call this structure the “unitarihedron.”<\/p>\n

    The unitarihedron encompasses, within a single abstract “jewel,” all<\/em> the computations that can ever be feasibly performed by means of unitary transformations, the central operation in quantum mechanics (hence the name).\u00a0 Mathematically, the unitarihedron is an infinite discrete space: more precisely, it’s an infinite collection of infinite sets, which collection can be organized (as can every set that it contains!) in a recursive, fractal structure.\u00a0 Remarkably, each and every specific problem that quantum computers can solve—such as factoring large integers, discrete logarithms, and more—occurs as just a single element, or “facet” if you will, of this vast infinite jewel.\u00a0 By studying these facets, my colleagues and I have slowly pieced together a tentative picture of the elusive unitarihedron itself.<\/p>\n

    One of our greatest discoveries has been that the unitarihedron exhibits an astonishing degree of uniqueness.\u00a0 At first glance, different ways of building quantum computers—such as gate-based QC, adiabatic QC, topological QC, and measurement-based QC—might seem totally disconnected from each other.\u00a0 But today we know that all of those ways, and many others, are merely different “projections” of the same mysterious unitarihedron.<\/p>\n

    In fact, the longer I’ve spent studying the unitarihedron, the more awestruck I’ve been by its mathematical elegance and power.\u00a0 In some way that’s not yet fully understood, the unitarihedron “knows” so much that it’s even given us new insights about classical<\/em> computing.\u00a0 For example, in 1991 Beigel, Reingold, and Spielman gave a 20-page proof of a certain property of unbounded-error probabilistic polynomial-time.\u00a0 Yet, by recasting things in terms of the unitarihedron, I was able to give a direct, half-page proof<\/a> of the same theorem.\u00a0 If you have any experience with mathematics, then you’ll know that that sort of thing never<\/em> happens: if it does, it’s a sure sign that cosmic or even divine forces are at work.<\/p>\n

    But I haven’t even told you the most spectacular part of the story yet.\u00a0 While, to my knowledge, this hasn’t yet been rigorously proved, many lines of evidence support the hypothesis that the unitarihedron must encompass the amplituhedron as a special case<\/em>.\u00a0 If so, then the amplituhedron could be seen as just a single sparkle on an infinitely greater jewel.<\/p>\n

    Now, in the interest of full disclosure, I should tell you that the unitarihedron is what used to be known as the complexity class BQP (Bounded-Error Quantum Polynomial-Time)<\/a>.\u00a0 However, just like the Chinese gooseberry was successfully rebranded in the 1950s as the kiwifruit<\/a>, and the Patagonian toothfish<\/a> as the Chilean sea bass, so with this post, I’m hereby rebranding BQP as the unitarihedron.\u00a0 For I’ve realized that, when it comes to bowling over laypeople, inscrutable complexity class acronyms are death—but the suffix “-hedron” is golden.<\/p>\n

    So, journalists and funders: if you’re interested in the unitarihedron, awesome!\u00a0 But be sure to also ask about my other research on the bosonsamplinghedron<\/a> and the quantum-money-hedron<\/a>.\u00a0 (Though, in recent months, my research has focused even more on the diaperhedron<\/em>: a multidimensional, topologically-nontrivial manifold rich enough to encompass all wastes that an 8-month-old human could possibly emit.\u00a0 Well, at least to first-order approximation.)<\/p>\n","protected":false},"excerpt":{"rendered":"

    Update (9\/24): This parody post was a little like a belch: I felt it build up in me as I read about the topic, I let it out, it was easy and amusing, I don’t feel any profound guilt over it—but on the other hand, not one of the crowning achievements of my career.\u00a0 As […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":false,"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,15,4],"tags":[],"class_list":["post-1537","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-csphysics-deathmatch","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1537","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=1537"}],"version-history":[{"count":8,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1537\/revisions"}],"predecessor-version":[{"id":1550,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1537\/revisions\/1550"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1537"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1537"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}