Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

Question

The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)

In the quantum counterpart, there is an $\mathcal{O}(n^2)$ algorithm due to Coppersmith, 1994, and also Deutsch (unpublished). Here $n$ is number of qubits.

Is this result known to be optimal?

There has been some approximate QFT algorithm that do better - see, $\mathcal{O}(n\log(n))$ due to Hales, 2002. But, I am restricting to exact algorithms only for this question.

Answer 1

Here's an $O(n \lg^2 n)$ construction of the QFT based on merging groups of phasing operations into multiplications:

You can verify the circuit works in Quirk.

The "reverse" gate reverses the order of the qubits; it's just $n/2$ swaps. The input gates indicate where the values multiply-added into the phase gradient register come from. The [::-1] means the input is ordered with the most significant qubit at the top instead of at the bottom. The phase gradient preparation assumes you can do arbitrarily fine rotations with cost $O(1)$; everything else is done exactly with just TOFFOLI+H.

The recursive relation for the cost is $T(n) = 2T(n/2) + O(M(n))$ where $M$ is the cost of multiplication. There are horrendously inefficient multipliers with asymptotic cost $O(n \lg n)$ achieving the $O(n \lg^2 n)$ I said at the start. More practically, using a Schonhage-Strassen multiplier, this construction has cost $O(n (\lg^2 n) (\lg \lg n))$. Or, with a Karatsuba multiplier, the cost is $O(n^{\lg_2 3})$.

You can verify the circuit works in Quirk.

In practice you would never, ever use this circuit because it's dumb to pay 100x more gates for exactness when nothing is trulyexact. Even ignoring the arbitrarily fine rotations, in practice there's no such thing as an exact Toffoli or an exact Hadamard. You can make rotation error arbitrarily small, but you can't make it 0. Everything is already approximate, so just use the much cheaper approximate QFT.

This specific construction is from two blog posts. The general idea was first found in "Fast parallel circuits for the quantum Fourier transform".

Answer 2

I think this is a good question. But the answers might depend on the precise meaning behind "exact" as even Coppersmith's improvement provides an approximate algorithm.

For example, Shor initially developed his very first algorithm for discrete logarithms over $\mathbb Z_p$ when $p-1$ is smooth - he used the quantum Turing machine model to provide an "exact" Fourier transform, and then went on to develop the general discrete logarithm and factoring algorithms, in the quantum Turing machine model, by finding an appropriately-sized smooth number over which he could apply the Fourier transform.

My understanding is that Coppersmith saw a preprint of Shor's algorithm, and recognized how to relate Cooley-Tukey's algorithm to the quantum setting. But, in his paper he keeps referring to his algorithm as an "approximate Fast Fourier Transform" algorithm, and mentions:

So the matrix entries of AFFT differ from those of FFT by a multiplicative factor of $\exp(i\varepsilon)$.

This sacrifice in precision improves over Shor's "exact" algorithm by a factor of $n$.

I would also refer to Gidney and Ekerå's paper on "how to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", which indicates that the quantum Fourier transform can be performed semi-classically but emphasizes that the QFT is negligible compared to the modular squaring.

---

Surely knowing of any improvement classically over Cooley-Tukey's $\mathcal O(n\log n)$ algorithm could have an immediate implication for the quantum version, but often even doing the Hadamard test - which is $\mathcal O(1)$ - would suffice. Such a Hadamard test is morally similar to a quantum Fourier transform but with only one bit of precision.