Source: Quantum Computation and Quantum Information
Given some orthonormal basis , the quantum Fourier transform is given by
Unitary
The linear transformation given by is unitary
Let , and consider . Writing out the product explicitly, we have (up to normalization)
We note that is an th root of unity, so . But so the summation must be . Trivially , so is unitary.
Circuit Construction
Let with computational basis . Write the binary decomposition and . Then we can decompose the QFT as
Define the phase rotation gate with . Given some input state , applying Hadamard takes us to the state . Applying from qubit for , we obtain
Successively performing this operation on yields
Finally, applying appropriate swap gates finishes the implementation of .