1
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

Mathematically, QFT and DFT are exactly the same thing. You can verify this by comparing the first equation on each of the Wikipedia pages. On Wikipedia these two differ by a minus sign in the exponent and by a normalization factor, but these are just conventions.

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).

By the way, the circuit that implements the QFT is a reflection of Cooley and Tukey's divide and conquer algorithm for FFT. When Cooley-Tukey splits the input in half, the QFT inspects one qubit. Ponder this and you will understand something about the power of quantum computers.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The signs in exponent of DFT and QFT are different and I don't know why. $\endgroup$ Apr 11 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.