Good news for once! A faster Quantum Fourier Transform
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 he and others knew related techniques but had never explicitly combined them). Of course, while the exact result was Platonically “known,” it wasn’t sufficiently well 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.
Another Update: Richard Cleve writes in to say that the approximate QFT circuits were known also—albeit, in an unpublished 2-page abstract by Ahokas, Hales, and himself from the 2003 ERATO conference, as well as a followup Master’s thesis by Ahokas. Unlike with the exact case, I’m not kicking myself trying to understand how I missed these.
Ironically, I hope this post helps get this prior work a well-deserved mention when the QFT is covered in introductory quantum information classes.
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 for the length of a curve) that were centuries old, then rediscovering things (like an efficient algorithm for isotonic regression) that were decades old, then rediscovering things (like BQP⊆PP) that were about a year old … until I finally started discovering things (like the collision lower bound) that were zero years old. This is the way.
In my last post, 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ïve 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 a consolation for advancing age and senility, and it’s called “students.”
This fall, I returned from my two-year leave at OpenAI to teach my undergrad Introduction to Quantum Information Science 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, 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 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 by dequantizing the K-P algorithm—a breakthrough 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.)
Today I’m delighted to announce that my undergrad quantum course has led to another quantum advance. One day, after my lecture, a junior named Ronit Shah came to me with an idea for how best to distinguish three 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, the Pretty Good Measurement (PGM), and the 2002 theorem that the PGM is optimal for distinguishing sets of states subject to a transitive group action.
Later, after I’d lectured about Shor’s algorithm, and one of its centerpieces, the O(n2)-gate recursive circuit for the Quantum Fourier Transform, 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.
This 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×2n matrix, so he was proposing to pass directly from 2n×2n to 2n/2×2n/2, rather than to 2n-1×2n-1?
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 log2n) gates, the first-ever improvement over O(n2), and also the approximate n-qubit QFT in O(n (log log n)2) gates, the first-ever improvement over O(n log n). He used fast integer multiplication algorithms to make the new recursions work.
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 unoriginal, or 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.
Last night Ronit’s paper appeared on the arXiv where you can read it.
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 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?
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.
Follow
Comment #1 January 23rd, 2025 at 1:13 pm
Rohit’s paper does not discuss the required gate depth of this recursive QFT. How does the gate depth compare to the traditional QFT?
Comment #2 January 23rd, 2025 at 1:26 pm
Joshua #1: Good question! I believe the depth is large (basically linear), much larger than in the usual QFT circuit. I’ll ask Ronit if he can say more.
Comment #3 January 23rd, 2025 at 1:40 pm
Sorry to rain on the parade, but I think this was found in 2000 by Cleve and Watrous ( http://arxiv.org/abs/quant-ph/0006004 ). I know this because in https://algassert.com/2016/06/14/qft-by-multiply.html I went through the same “damn someone already found this” experience.
Outside quantum computing IIRC this factorization of the FFT is also one the key ideas behind Martin Fürer’s multiplication algorithm ( https://ivv5hpp.uni-muenster.de/u/cl/WS2007-8/mult.pdf ). IIRC the idea is that, when you decompose in this way instead of the usual way, the n/2 finest grained angles only appear in the overall circuit 1 time during the first recursive step (instead of in n/2 of the recursions; see the last diagram in https://algassert.com/post/1620 for a clear example of what I mean). So if you can find a group with a primitive root of unity g where where powers of g^(2^k) are cheap to multiply by, then you will still get a good recursive relation in youur asymptotic costs while being able to divide the problem into 2^k times more pieces. This makes it possible to beat Schönhage–Strassen multiplication.
Comment #4 January 23rd, 2025 at 1:44 pm
Given that some modular exponentiation circuits use multiple QFTs, it would be interesting to come up with more succinct mod-exp circuits by leveraging new QFT ideas. Of course, circuit depth could become a problem here.
Comment #5 January 23rd, 2025 at 1:57 pm
Craig Gidney #3: Shoot, I knew the Cleve-Watrous result about depth! How did we all miss that the same paper also has a result about size? Well, what about the approximate QFT circuit; is that one new?
Comment #6 January 23rd, 2025 at 2:21 pm
For approximations I’m aware offhand of similar truncation ideas in https://algassert.com/post/1620 and https://arxiv.org/abs/1803.04933 but with a total cost of O(n lg n) [assuming the desired error is polynomial in n] instead of O(n (lg lg n)^2). https://algassert.com/post/1620 is painfully close to saying “oh and of course you can combine the MAC idea and the truncation idea” but somehow never does. So as far as I know that part of the paper is new, though it’s very much a near miss.
I guess I should also say I consider rediscovery a normal part of science, and a very good sign in a student.
Comment #7 January 23rd, 2025 at 2:25 pm
“For my trouble, I was condemned about equally by leftists for my right-wing sympathies and by rightists for my left-wing ones.”
Sounds like you found that tightrope!
Comment #8 January 23rd, 2025 at 3:04 pm
Craig Gidney #6: OK, thanks for bringing this to our attention! While I wait for a reply from Ronit, I’ll add a disclaimer to the post. It sounds like the new approximate circuit should still be publishable as a note, giving proper credit to Cleve and Watrous for the exact circuit and to your webpage for getting “painfully close.”
Meanwhile, the question for me is: how can I fix my advising process to prevent this from recurring? I did spend hours searching Google Scholar to check if the result was already known, and I did reach out to four separate experts, none of whom thought it was known. I just didn’t reach out to the exact right experts, and I missed the one relevant paper (Cleve-Watrous), because I “knew” that one was just about parallelization.
I think the truth we’ve uncovered is that, while O(n log2 n) circuits for exact QFT were Platonically “known,” they weren’t known to be known, even by most of the quantum algorithms community. Hopefully this very blog post will help fix that state of affairs.
Comment #9 January 23rd, 2025 at 3:18 pm
My personal technique was to perfect the art of not feeling bad when I got scooped by over two decades. Actually, quantum computing was kind of refreshing compared to classical algorithms because it was only two decades instead of five.
I assume the way I found the paper originally was by doing a google scholar search for things like quantum fourier transform. I wouldn’t have had the blinders of knowing the paper’s main result. It’s quite common for papers to have extra results… maybe knowing the main result is a handicap to finding those.
I did a quick check to see if ChatGPT was able to point towards the paper when prompted. It’s not; hallucinates like crazy if you ask for references.
Specifically for circuit construction results, I’d recommend pinging me or Greg Kahanamoku-Meyer or Dmitri Maslov (especially Dmitri for anything Clifford).
Comment #10 January 23rd, 2025 at 6:34 pm
The earlier topic of optimal measurement of qutrits is evocative to me. There is a universal coefficient of ln(3) that appears in the modes of decay of certain black holes, conjectured by Shahar Hod and later proved by Lubos Motl. In the 2000s, there were researchers in loop quantum gravity who wondered if it was a clue to something fundamental, but no one seems to have touched it in the qubitzer era. Lubos himself made a passing remark that the decay behavior resembled a “tripled Pauli statistics”. A handful of people have taken this seriously, and one of them (Carl Brannen) tried to implement it using mutually unbiased bases, though not in the context of quantum gravity. And there seems to be a connection between MUBs, POVMs, and quantum state reconstruction… My intuition is telling me to connect the efficiency of PGMs with the fast scrambling property of quantum black holes, but I don’t know enough to state it logically… I await the rise of the Qutritzers who will resolve these questions.
Comment #11 January 23rd, 2025 at 6:44 pm
Scott: I suspect that it isn’t a coincidence that both of these truly remarkable undergraduates were taught by you. In addition to your direct research contributions, you seem to have a real knack for bringing out the very best in the students whom you teach.
Comment #12 January 23rd, 2025 at 9:56 pm
I can understand the result about QFT circuit size in my old paper with John being overlooked. The emphasis was on the depth result, which we thought had more currency (although the size result is stated in the abstract).
Something else: In 2003, Graeme Ahokas, Lisa Hales, and I had a talk at a conference about the computing the approximate case in size O(n (loglog n)^2 logloglog n). The logloglog n factor was because, back then, Schönhage-Strassen was the best multiplication algorithm known.
The conference was the ERATO Conference on Quantum Information Science, Kyoto, Japan, September 5, 2003, and there was a two-page abstract entitled “The complexity of quantum Fourier transforms and integer multiplication” posted on their web site (but that web site no longer appears to exist). That abstract, which is essentially the whole paper, is available at: https://cs.uwaterloo.ca/~cleve/pubs/2004EfficientQft.pdf
In hindsight, we should have posted this somewhere like arXiv. I’m not exactly sure why we didn’t, but I vaguely remember that we had plans to work on a paper with more results for publication, but that never materialized.
Comment #13 January 24th, 2025 at 4:31 am
If I invent something relatively simple I always assume someone should’ve found it before 🙂 For example, I once found that for symmetric bipartite states there is always a symmetric Schmidt decomposition (where each summand is a symmetric tensor product). I haven’t seen it the literature, but I’m sure someone has already found it and used in their work.
Anyway, even if the result is not new it’s always interesting to see how they derived it. Alternative ways of thinking have their own worth.
Comment #14 January 24th, 2025 at 8:14 am
As a follow-up to my #12, it occurred to me this morning to check whether Graeme Ahokas’s Master’s Thesis contained a result about the approximate case, and it does (among other results, including about Hamiltonian simulation). His 2004 thesis is available at
https://prism.ucalgary.ca/items/747b4b9d-2e67-4f90-8475-8ec6d236a419
I agree with Graig Gidney’s comment #6 that “rediscovery a normal part of science, and a very good sign in a student”.
Comment #15 January 24th, 2025 at 9:40 am
Richard Cleve #12, #14: Thanks so much! I’ll add an additional update to the post, that the approximate circuits were known also (albeit, in an ERATO 2-page abstract and a Master’s thesis not on the arXiv—so unlike with the exact case, I’m not slapping myself wondering how I could’ve missed these 🙂 ).
I hope that, ironically, this post succeeds at giving your and others’ prior work on this problem some more attention! It definitely deserves a mention when the QFT is covered in introductory QIS classes.
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 for the length of a curve) that were centuries old, then rediscovering things (like an algorithm for isotone regression) that were decades old, then rediscovering things (like BQP⊆PP) that were about a year old when I discovered them … until I finally started discovering things (like the collision lower bound) that were zero years old. This is the way.
Comment #16 January 24th, 2025 at 11:12 am
Incidentally, it makes me feel a bit better that the ChatGPT o1 model just explained to me in great detail why nothing better than O(n2) is known for the exact n-qubit QFT, or O(n log n) for the approximate QFT! 🙂
Comment #17 January 24th, 2025 at 7:21 pm
In view of Scott and Craig’s comments about missing “extra” results hidden in papers (and in shameless self-promotion) I wanted to mention that in https://arxiv.org/abs/2403.18006 we used the recursive exact QFT construction from Cleve+Watrous to construct an entirely *in-place* (no ancillas) exact QFT using O(n^(1+eps)) gates for any eps>0, by building off of classical Toom-Cook multiplication. (See end of Section 3). Important to note that the constant factors blow up as eps gets smaller. 🙂
Comment #18 January 27th, 2025 at 8:51 am
Looks like all the claims that further AI progress relies on trillion$ investments seem now very questionable…
Bad news for the US stock market and Altman’s bonus, but good news for those worried about the impact of AI resources on climate change (all things being equal).
Comment #19 January 28th, 2025 at 6:07 pm
Thank you for sharing this lovely work, Scott!
I am curious if what Ronit has found is related to a particular approximate MPO realization of QFT—the one which is based on Chebyshev-Lobatto interpolation from the recent work https://arxiv.org/abs/2404.03182 ? This work describes a new “translation invariant” MPO approximation of the QFT—an elegant construction based on classical interpolation theory. Citing the last sentence of this paper: “Whether other interpolative constructions can yield more efficient quantum circuits that approximate the QFT is an interesting open question.”
There might be some general theory/recipe for different approximate QFT constructions based on different interpolation methods.
Comment #20 January 28th, 2025 at 10:38 pm
Scott, I have a question that’s not related to this blog post, but I hope you’ll be interested to answer.
How do you feel about the prospects of LLMs automating much of the theoretical/computational work in quantum computing in the near future? And, what advice would you give someone in the field early in the career, torn between theory and experiment?
Right now, LLMs are not that close to doing the kind of theoretical work done at quantum computing labs and companies. But they’re not lightyears away either. The kind of progress needed to go from where LLMs were 10 years ago, to getting a B on your final exam today (https://scottaaronson.blog/?p=7209), seems comparable to the kind of progress required to from the current state of LLMs to being able to automate away most, but not all, of the theoretical jobs in quantum computing.
Should people early in their careers take this state of affairs into account? For context, I do theoretical work in quantum error correction. While I like to think my research is good quality, I don’t think I’d make the cut if LLMs reduce demand for people with my skills by 90%. Early on in my PhD, I thought hard about whether I wanted to do theory or experiment, and eventually settled on theory. Sometimes I seriously doubt that decision. At 2.5 years into the PhD, it’s a little late to switch, but not totally out of the question…
Comment #21 January 29th, 2025 at 12:27 am
Alex Fischer #20: Those are enormous questions—ones that (as you can imagine) I now get all the time from young people. I’ve been wrestling with these questions myself.
I don’t know if this is much comfort, but I’m pretty confident that, at whatever time AI is able to automate theoretical quantum computing research, it will soon also be able to automate the vast majority of what humans do. In other words: I don’t see that working either with real physical objects, or with “squishy” subjects like art or literature or emotions, provides any real protection here. It’s true that robotics lags behind other areas of AI, but it should catch up with more training data. Meanwhile, lots of people in “squishy” fields are already having their jobs threatened by generative AI, which turns out to be spectacular at picking up on subtle emotional nuances.
To put it another way: I can see the case for continuing to do the creative work you love, because for now you’re still needed to do that work, and if someday AI can do it better … well then, you’ll deal with that day when it comes, just like the rest of the world will! Or maybe because there’s work you desperately want to do, regardless of whether AI will soon do it better (as chess grandmasters, long-distance runners, etc. etc. continue to perfect their crafts despite having long ago been surpassed by machines). Or there’s work you really want humans to be the first to have done (in which case, you should probably get cracking!).
I can also see the case for dropping everything else to work on AI, or (especially) AI policy and alignment.
But I find it harder to see the case for dropping a creative pursuit that you love for a different creative pursuit that you love less, in an attempt to outrun AI. That seems to me like a loser’s game, like something that would buy you a few years at most in any future where it’s relevant at all.
Comment #22 January 29th, 2025 at 11:05 am
It’s quite cute to see people still mention AI alignment when hundreds of thousands of people are currently installing locally a Chinese LLM with advanced reasoning logic that noone knows what data it was trained on… but it’s a safe bet that it must have included thousands of hacking code examples…
Comment #23 January 29th, 2025 at 12:22 pm
Thanks for the response Scott. Experiment really isn’t substantially less interesting to me; when I say “I thought hard about whether I wanted to do theory or experiment”, I mean “both theory and experiment were appealing to me, and I wasn’t sure which one appealed to me more, and after much deliberation I decided on theory but wasn’t supremely confident in the decision”. Hence I’m open to switching in response to new information, and wouldn’t really view it as giving up on something I love as much as switching to something I love a similar amount.
Your comment “there’s work you really want humans to be the first to have done” does resonate with me. I care deeply about what error correcting codes, fault-tolerant procedures, and decoders we use to implement fault-tolerant quantum computation. If those codes, etc end up being AI-generated, especially if humans don’t fully understand what the AI gave us, I’ll regard that as a kind of aesthetic failure, even if it would be an enormous technical success.
Comment #24 January 30th, 2025 at 8:29 pm
If FFT is to fast polynomial multiplication, then what does QFFT correspond to?
Comment #25 February 14th, 2025 at 11:33 am
Scott, interesting mix: revealing forgotten new results and scientific processes! We are glad that students are following through, even if they are “reinventing the wheel”. Could this QFT gate open new directions, e.g. in algorithms beyond fabrication? Keep your fingers crossed for Ronit – theory based on such minds, even if it chooses industry. Blog as a tool for sharing knowledge – brilliant!