What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm? I cannot seem to understand the role or goal of Quantum Fourier Transformation in Shor's integer factorization algorithm. Is it used to collapse all quantum states into one, in which it has a factor of a given input $n$?
To do factoring, Shor's algorithm presents a way of finding the the following problem. If I know some natural numbers $g$ and $N$, with $g &lt; N$, where $\gcd(g, N) = 1$, what is the smallest $r &gt; 0$ such that $g^r = 1 \bmod N$. This is called the problem of finding the order of $g$ modulo $N$.

By Euler's theorem, there will be some such $r$ because $g^{\phi(N)} = 1 \bmod N$ for all $\gcd(g, N) = 1$, where $\phi(N)$ is Euler's Totient function.

The annoying thing about quantum computing, as you may have figured out by this point, is that you can create some arbitrary superposition of states and do computation on all of those states in parallel, but then when you want to get an actual value you only get to see one of those answers, chosen at random from the answer distribution. Say for instance we set $a$ to be some quantum state that is the superposition of all integers from 1 to 10 (each with equal probability). Then we compute $b=2*a$. It will multiply all of the states by 2 in parallel and we will get a quantum state that is the superposition of all even numbers from 2 to 20. Now if we "open" the state of $b$ we get a random even number from 2 to 20. Which is pretty useless. We could have just opened $a$ first and done the computation ourselves.

Now, the Fourier transform takes a function and computes the "waves" that it is composed of. For instance the image below (from this site) shows the wave forms of different instruments and their corresponding Fourier transforms. In particular, notice the spikes in the Fourier transform graphs. The first spike corresponds to the period of the function. The other spikes show various harmonics that exist on top of this.

 

Now, back to finding the order of $g$ modulo $N$. You start with setting $a$ to be a uniform superposition of all numbers from 0 to $q-1$, for some $q &gt;&gt; N$.

You then compute $(a, g^a \bmod N)$. This will now be a superposition of $q$ tuples. 

Now comes the important part. $g^a \bmod N$ is periodic. Specifically, if $r$ is the lowest non-zero integer such that $g^r = 1 \bmod N$, then $g^a \bmod N$ is periodic with period $r$. So, like with the musical instruments, if you were to plot $a$ against $g^a \bmod N$, there would be some visible repeated fundamental frequency and a number of other harmonics on top of this. So now if you compute the Fourier transform on $(a, g^a \bmod N)$ you will get a function showing how often different frequencies appear. 

Now we look at the register holding the value of the frequency. There is some chance that we will get one of the higher harmonics, but there is a pretty good chance that we will get the fundamental frequency. This frequency corresponds to the period of $g^a \bmod N$, namely $r$. Since this experiment has a certain probability of failing (picking one of the higher harmonics). But if you repeat it some polynomial number of times, you can make the probability of it failing in all of those times as low as you want.