Lazy Fourier Transform (LFT)
For an input vector $ \mathbf{x} $:
- Pad $ \mathbf{x} $ with zeros until its length is a power of 2.
- Pad $ \mathbf{x} $ with more zeros until its length is a power of 3.
- Give ‘em a billion more zeros.
- For a random prime $ p $, pad $ \mathbf{x} $ with more zeros until its length is a power of $ p $.
- OK, now $ \mathbf{x} \equiv 0 $ approximately, hence its Fourier transform is the zero vector, so just return zero.
Slow Fourier Transform (SFT)
For an input vector $ \mathbf{x} $:
- Initialize $ \mathbf{y}=0 $.
- Find a Gaussian fit for $ \mathbf{x} $.
- The Fourier transform of a Gaussian is a Gaussian! Add the transformed Gaussian to $ \mathbf{y} $, and subtract the original Gaussian from $ \mathbf{x} $.
- Repeat until $ \mathbf{x}=0 $, and then return $ \mathbf{y} $.
Complexity: I dunno, does it even converge?
Quantum Fourier Transform (QFT)
- Wait until they build a good enough quantum computer with a large number of qubits.
- Run the well-known QFT algorithm, that runs in only $ O(\log n) $.
Oh, you wanted your output to be expressed as a usual vector, and it’s inconvenient for you to have its components registered in the quantum phases of a wavefunction? Well, no problem! There’s this method… *mumble* phase estimation circuit… *mumble* and that’s it, good luck!
Bogo Fourier Transform (BFT)
For an input vector $ \mathbf{x} $:
- Generate a random vector $ \mathbf{y} $.
- Compute the inverse Fourier transform of $ \mathbf{y} $, denoted $ \text{FT}^{-1} [ \mathbf{y} ] $.
- If $ \mathbf{x} = \text{FT}^{-1} [ \mathbf{y} ] $ return $ \mathbf{y} $, otherwise go back to step 1.
Remark: How do we compute the inverse Fourier transform on the second step? Ummm… there’s a MATLAB function that does that, right? That should do it.