What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

Question

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$?

Answer 1

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 < N$, where $\gcd(g, N) = 1$, what is the smallest $r > 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 >> 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.

Answer 2

TL;DR: Very simplified, the Quantum Fourier Transform amplifies a periodicity $p$, where $g^\frac{p}{2} - 1 = a$ and we can find a factor of $N$ with Euclid's algorithm by performing $\text{Euclid}(a, N)$.

---

Shor's algorithm in one sentence (basically):

You start with some random guess that might share a factor with $N$ (very likely doesn't) and the algorithm "transforms" the first guess to a much better guess, which does share a factor with $N$.

Your guess then could be a direct factor of $N$ (which would then also be the solution, since $N = p \times q$), but doesn't has to be, it can also be a number that shares a factor with $N$. This is already enough because of Euclid's algorithm. With Euclid's algorithm you can find a common factor between two numbers really fast with very basic math.

The trick of Shor's algorithm relies on a simple mathematical fact:

For two numbers with no common factors $a$ and $b$, there exists a number $m$ and $p$ so that $$a^p - 1 = m \times b$$

($p$ here is just some number, which isn't the $p$ from $N = p \times q$).

An example:

$7$ and $15$

$7^4 - 1 = 160 \times 15$.

So for $N$ you would take a guess $g$ and it's guaranteed that some number $p$ exists that $g^p - 1 = m \times N$.

Also notice that $g^p - 1$ $\implies$ $(g^\frac{p}{2} + 1) \times (g^\frac{p}{2} - 1)$.

And for our example of $7$ and $15$:

$7^\frac{4}{2} - 1 = 48$

We then use Euclid's algorithm to find shared factors of $15$ and $48$:

$\text{Euclid}(15, 48) = 3$.

And then we have our solution, since $15 = 3 \times 5$.

---

But how does the quantum fourier transform play a role in this?

Well, the problem is that you can't easily find the number $p$ with a classical computer and you need $p$ to make all of the above work.

A quantum computer can calculate a lot of possible answers for one input by using something called quantum superposition.

But that's also a problem, since you can only retrieve one answer from a quantum computer when you measure the superposition. And it would likely give you a wrong answer, since all answers are evenly distributed.

You can take any number $x$ and get a remainder $r$ by performing the calculation:

$$g^x = m \times N + r$$

The important part here is that this remainder $r$ has a periodicity! And this periodicity is exactly $p$.

So

$$g^x = m_1 \times N + r$$

$$g^{x+p} = m_2 \times N + r$$

$$g^{x+2p} = m_3 \times N + r$$

$$\vdots$$

Notice how $r$ always remains the same number.

So we see now, that the power p we're looking for, has a repeating property.

And this is exactly where the Quantum Fourier Transform plays an important role, because with the Quantum Fourier Transform we can find this periodicity $p$.

We still have all the possible answers of $p$ in the superposition in a quantum computer, but the QFT cancells out the wrong answers (like noise cancelling headphones cancell out noise) and it amplifies the correct answer.

---

As soon as we perform a measurment of the quantum state of the quantum computer we get the single quantum state $$\frac{1}{p}$$

We can then invert $\frac{1}{p}$ and get $p$. If $p$ is even we can then finally find a number (with $g^\frac{p}{2} - 1$) who has common factors with $N$. We use Euclid's algorithm to get the common factor and this factor then is obviously one factor of $N$.

If $p$ is not even then you have to guess again with a different number. On average the $p$ you get after the whole procedure has a probability of $37.5 \%$ chance of being even.