Good news for once! A faster Quantum Fourier Transform

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 Platonica…