{"id":8593,"date":"2025-01-23T12:58:38","date_gmt":"2025-01-23T18:58:38","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=8593"},"modified":"2025-01-24T10:07:40","modified_gmt":"2025-01-24T16:07:40","slug":"good-news-for-once-a-faster-quantum-fourier-transform","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=8593","title":{"rendered":"Good news for once! A faster Quantum Fourier Transform"},"content":{"rendered":"\n

Update:<\/mark><\/strong> In the comments, Craig Gidney points out<\/a> that Ronit’s O(n log2<\/sup> n) quantum circuits for the exact QFT were already published by Cleve and Watrous<\/a> in 2000 (in a paper whose main point was something else, parallelization). Ronit’s O(n (log log n)2<\/sup>) circuits for the approximate QFT still appear to be new (Gidney says he and others knew related techniques<\/a> but had never explicitly combined them). Of course, while the exact result was Platonically “known,” it wasn’t sufficiently well<\/em> known that any of the four quantum algorithms experts I’d consulted had heard of it! Hopefully this very post will go some way toward fixing the situation.<\/p>\n\n\n\n

Another Update:<\/mark><\/strong> Richard Cleve writes in<\/a> to say<\/a> that the approximate QFT circuits were known also—albeit, in an unpublished 2-page abstract<\/a> by Ahokas, Hales, and himself from the 2003 ERATO conference, as well as a followup Master’s thesis<\/a> by Ahokas. Unlike with the exact case, I’m not kicking myself trying to understand how I missed these<\/em>.<\/p>\n\n\n\n

Ironically, I hope this post helps get this prior work a well-deserved mention when the QFT is covered in introductory quantum information classes.<\/p>\n\n\n\n

Meanwhile, my hope that Ronit returns to do more theory is undiminished! When I was a kid, I too started by rediscovering things (like the integral<\/a> for the length of a curve) that were centuries old, then rediscovering things (like an efficient algorithm for isotonic regression<\/a>) that were decades old, then rediscovering things (like BQP\u2286PP<\/a>) that were about a year old \u2026 until I\u00a0finally<\/em>\u00a0started discovering things (like the collision lower bound<\/a>) that were zero years old. This is the way.<\/p>\n\n\n\n

\n\n\n\n

In my last post<\/a>, I tried to nudge the arc of history back onto the narrow path of reasoned dialogue, walking the mile-high tightrope between shrill, unsupported accusation and na\u00efve moral blindness. For my trouble, I was condemned about equally by leftists for my right-wing sympathies and by rightists for my left-wing ones. So today, I’ll ignore the fate of civilization and return to quantum computing theory: a subject that’s reliably brought joy to my life for a quarter-century, and still does, even as my abilities fade. It turns out there is<\/em> a consolation for advancing age and senility, and it’s called “students.”<\/p>\n\n\n\n

This fall, I returned from my two-year leave at OpenAI to teach my undergrad Introduction to Quantum Information Science<\/a> course at UT Austin. This course doesn’t pretend to bring students all the way to the research frontier, and yet sometimes it’s done so anyway. It was in my first offering of Intro to QIS, eight years ago, that I encountered the then 17-year-old Ewin Tang<\/a>, who broke the curve and then wanted an independent study project. So I gave her the problem of proving that the Kerenidis-Prakash quantum algorithm<\/a> achieves an exponential speedup over any classical algorithm for the same task, not expecting anything to come of it. But after a year of work, Ewin refuted my conjecture<\/a> by dequantizing the K-P algorithm<\/a>—a breakthrough<\/a> that led to the demolition of many other hopes for quantum machine learning. (Demolishing people’s hopes? In complexity theory, we call that a proud day’s work.)<\/p>\n\n\n\n

Today I’m delighted to announce that my undergrad quantum course has led to another<\/em> quantum advance. One day, after my lecture, a junior named Ronit Shah came to me with an idea for how best to distinguish three<\/em> possible states of a qubit, rather than only two. For some reason I didn’t think much of it at the time, even though it would later turn out that Ronit had essentially rediscovered the concept of POVMs<\/a>, the Pretty Good Measurement<\/a> (PGM), and the 2002 theorem<\/a> that the PGM is optimal for distinguishing sets of states subject to a transitive group action.<\/p>\n\n\n\n

Later, after I’d lectured about Shor’s algorithm<\/a>, and one of its centerpieces, the O(n2<\/sup>)-gate recursive circuit for the Quantum Fourier Transform<\/a>, Ronit struck a second time. He told me it should be possible to give a smaller circuit by recursively reducing the n-qubit QFT to two (n\/2)-qubit QFTs, rather than to a single (n-1)-qubit QFT.<\/p>\n\n\n\n

This<\/em> was surely just a trivial confusion, perfectly excusable in an undergrad. Did Ronit perhaps not realize that an n-qubit unitary is actually a 2n<\/sup>\u00d72n<\/sup> matrix, so he was proposing to pass directly from 2n<\/sup>\u00d72n<\/sup> to 2n\/2<\/sup>\u00d72n\/2<\/sup>, rather than to 2n-1<\/sup>\u00d72n-1<\/sup>?<\/p>\n\n\n\n

No, he said, he understood that perfectly well. He still thought the plan would work. Then he emailed me a writeup—claiming to implement the exact n-qubit QFT in O(n log2<\/sup>n) gates, the first-ever improvement over O(n2<\/sup>), and also<\/em> the approximate n-qubit QFT in O(n (log log n)2<\/sup>) gates, the first-ever improvement over O(n log n). He used fast integer multiplication algorithms to make the new recursions work.<\/p>\n\n\n\n

At that point, I did something I’m still ashamed of: I sat on Ronit’s writeup for three weeks. When I at last dug it out of my inbox and read it, I could discover no reason why it was wrong, or<\/em> unoriginal, or<\/em> unimportant. But I didn’t trust myself, so with Ronit’s permission I sent the work to some of my oldest quantum friends: Ronald de Wolf, Cris Moore, Andrew Childs, and Wim van Dam. They agreed, after some back-and-forth, that the new circuits looked legit. A keystone of Shor’s algorithm, of quantum computing itself, and of my undergrad class had seen its first real improvement since 1994.<\/p>\n\n\n\n

Last night Ronit’s paper appeared on the arXiv<\/a> where you can read it.<\/p>\n\n\n\n

In case anyone asks: no, this probably has no practical implication for speeding up factoring on a quantum computer, since the QFT wasn’t the expensive part of Shor’s algorithm anyway—that’s the modular exponentiation—and also, the O(n log n) approximate QFT would already have been used in practice. But it’s conceivable that Ronit’s circuits could<\/em> speed up other practical quantum computing tasks! And no, we have no idea what’s the ultimate limit here, as usual in circuit complexity. Could the exact n-qubit QFT even be doable in O(n) gates?<\/p>\n\n\n\n

I’d love for Ronit to continue in quantum computing theory. But in what’s surely a sign of the times, he’s just gone on leave from UT to intern at an AI hardware startup. I hope he returns and does some more theory, but if he doesn’t, I’m grateful that he shared this little gem with us on his way to more world-changing endeavors.<\/p>\n","protected":false},"excerpt":{"rendered":"

Update: In the comments, Craig Gidney points out that Ronit’s O(n log2 n) quantum circuits for the exact QFT were already published by Cleve and Watrous in 2000 (in a paper whose main point was something else, parallelization). Ronit’s O(n (log log n)2) circuits for the approximate QFT still appear to be new (Gidney says […]<\/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],"tags":[],"class_list":["post-8593","post","type-post","status-publish","format-standard","hentry","category-complexity","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\/8593","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=8593"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8593\/revisions"}],"predecessor-version":[{"id":8600,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/8593\/revisions\/8600"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}