The Quantum Fourier Transform - QFT

The Fourier Transform operation is very useful, with a wide range of applications in physics, engineering, mathematics, etc. The discrete Fourier transform takes a vector of complex numbers to another vector, whose components are associated to the input vector, through the definition  

In Quantum Computing, the Quantum Fourier Transform (QFT) is behind the exponential gain in the speed of algorithms [10] such as Shor s factoring algorithm [11,12], The operator QFT can be implemented using only Q(n ) operations, whereas its classical analogue, the Fast Fourier Transform (FFT) requires about Q(n2 ) operations. Therefore, QFT is implemented exponentially faster than the FFT. 

The QFT is an unitary transformation (see problems), which takes each eigenstate of the system to a superposition, as described by Equation (3.5.5), where n is the number of qubits in the system  

An alternative definition of the QFT illustrates better the quantum operations needed for its implementation  

The relation above, Equation (3.5.6), is very useful, because it indicates the necessary operations to be performed on each qubit for the implementation of the QFT. For instance, starting from the first qubit, the first step is to apply a Hadamard gate, followed by a relative phase change, controlled by the other qubits, of the system. One can see from Equation (3.5.6) why a relative phase change is needed. This operation can be performed by some applications of the logic gate Rk.  

---