# How to derive quantum Fourier transform from discrete Fourier transform (DFT)?

I am interested in Shor's algorithm, and I am reading several papers that related to the quantum Fourier transform (QFT).

I know the there is a difference between the output of QFT and DFT (DFT). But I do not know how to derive QFT from DFT. I do not know how to link from QFT and DFT, and maybe I have not comprehend all the differences between QFT and DFT.

The difference between Quantum Fourier Transform and classical Fast Fourier transform is in the speed and in the way the data is represented physically. Classically, a dimension $n$ vector is represented using $n$ floating point numbers. On a quantum computer, the QFT operates on the wave function of $\log_2 n$ qubits, an exponential space savings. The classical FFT runs in time $O(n\log n)$ and the QFT runs in time $O((\log n)^2)$ where again $n$ is the dimension of the vector. Note that the classical FFT must take time $O(n)$ to even read the input!
It should also be noted that the classical and quantum versions differ in another important respect, as a consequence of the way the data is stored. After the classical FFT algorithm completes, you have the entire output vector to do whatever you want with (e.g. print out the $100^{\textrm{th}}$ component of the vector or whatever). The QFT leaves the answer in a quantum state, which you can think of as a sort of generalized probability distribution, and you can do certain measurements to get certain types of information out, but you have to be crafty. Shor's algorithm is of course the canonical place to look for an example here, although Simon's algorithm illustrates many of the same concepts without having to deal with the computational tedium of Shor's algorithm (Simon uses the Hadamard rather than Fourier transform but conceptually there is not much difference).
The above answer appears to be mostly correct however, I'm not sure about the first paragraph. The definitely differ by a normalization factor, but the exponent appears the same for both. One should be able to say that algorithmically, if we input a sequence of qubits in vector form then, we should get QFT = $$\sqrt{N}$$DFT, where $$N$$ is the number of qubits. Please correct me if I'm wrong.