How does one implement the QFT? The same way as one would do FFT, but with quantum gates? I.e. taking O(n*log(n)) gates with two inputs and two outputs? I'm imagining that there's some sort of a vector of quantum (complex) amplitudes left after the exponentiation that needs to be transformed.
No, QFT requires only O(log(n)^2) gates. It can be described by using a recursion. That is, QFT on 2^n values (n qubits) can be computed using QFT on 2^(n-1) values (n-1 qubits).
The QFT is the Cooley-Tukey FFT algorithm [1] expressed as a tensor network [2].
Cooley-Tukey has two main steps that are repeated recursively: bulk replacing a,b with a+b,a-b along bit boundaries, and applying twiddle factors. The bit-boundary a,b->a+b,a-b part becomes a Hadamard gate and the bit twiddling becomes a set of phase gates. Also there's some re-ordering but that's not the meat.
The actual quantum circuit: [4].
The quantum circuit is simple enough that it's a really solid mnemonic for remembering Cooley-Tukey, if you know how to translate it. There are also various ways to optimize the gate count or gate depth of this circuit, and these optimizations translate into changes to the classical FFT (though they are not always optimizations after translation) [5].
