# Simplified explanation of Shor/QFT transformation as thumbtack

As a non-mathematician/software programmer I'm trying to grasp how QFT (Quantum Fourier Transformation) works.

And this blogpost: https://www.scottaaronson.com/blog/?p=208

I've got a basic understanding on how you can calculate/construct the period using interference. But while trying to explain this to a colleague I ran into a problem. I used the following examples, N=15, a=7, so the period I'll need to find is r=4.

The pattern is: 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)

If I imagine the wheel (like in the YouTube video) or a clock (like the blogpost) I can see that the circle with 4 dots/clock with 4 hours creates a constructive pattern and the others do not.

But what happens with a circle with 2 dots, or a clock with 2 hours, those will have get the same magnitude/constructive pattern as 4? It loops twice as fast, but other than that, same result?

How does the QFT cope with this?

(Bonus: Can you explain in laymans terms without too much complicated math?)

Let me attempt to give a rather unconventional answer to this question:

As a non-mathematician/software programmer I'm trying to grasp
how QFT (Quantum Fourier Transformation) works.


Suppose that we have a quantum computer which is able to manipulate $n$ qubits. The quantum state of such a quantum computer precisely describes the current state of this quantum computer. It is pretty well-known that we can express this quantum state as a vector of $2^n$ complex numbers. Let's try to visualize these complex numbers in a compact way.

To that end, consider a horizontal line, on which $2^n$ points are depicted. They are labeled corresponding to their respective position on the line, i.e., the first point is labeled with $|0\rangle$, and the last points is labeled by $|2^n-1\rangle$. We can see this in the picture below.

Now, try to picture that at every point, depicted above, this line punctures a circle of radius $1$ right through the middle. That is, there are $2^n$ circles placed exactly at the points depicted above, and the line connects the middles of all these circles. I have tried to depict this in the image below, but my 3D drawing skills are not exactly top-notch, so you will have to excuse me for that.

The nice thing of this picture above is that it can uniquely represent the state of any $n$-qubit quantum computer by marking exactly one point in all of the circles. More explicitly, any quantum state of a $n$-qubit quantum computer can be depicted in the above picture by drawing one cross ($\times$) in all of the circles. Conversely, any such drawing represents a quantum state, as long as the squares of the distances of the crosses to the center point sum to $1$. In other words, if we calculate all the distances of the marked points to the center points, then square these distances, and then add them all up, we require that the result equals $1$. An example state is shown below:

Throughout the execution of a program, the state of the quantum computer is constantly changing, and as such, so is the visual representation. Hence, throughout the execution of a quantum program, the marked points (the $\times$s), are constantly moving around, within the boundaries of their respective circles.

Within this framework, the Quantum Fourier Transform is just a very specific way to move the marked vertices around. We will make this explicit in the case of a $3$-qubit quantum computer, on which a $3$-qubit Quantum Fourier Transform is executed.

To that end, suppose that we have the $3$-qubit system in the following state, i.e., where the cross is all the way at the edge in the $|0\rangle$ circle, and all the others are exactly at the center. It is an exercise for the OP to check that indeed the square of the distances of the marked points to the center points sum to $1$. We refer to this state as the $|0\rangle$ state.

The question is now what happens to the quantum state when we apply the Quantum Fourier Transform. It turns out that, when the Quantum Fourier Transform is applied to the state shown above, the resulting state of the quantum system becomes:

Here I added the red dashed line passing through all the marked points just for extra convenience. All the marked points are on the exact same location in the circles, namely precisely above the center point at a height of $1/\sqrt{8}$.

Similarly, we can have a look at the action of the Quantum Fourier Transform on other states. Consider for example the $|1\rangle$ state:

Now, if we apply the Quantum Fourier Transform, the resulting state becomes:

We can see that the resulting state becomes some kind of helix shape. Moreover, observe that if we were to add one extra circle to the right of the rightmost state, then the helix would complete exactly one revolution.

It turns out that the other states behave similarly under the Quantum Fourier Transform, but that the period of the helix changes. More precisely, if we start out with the state $|j\rangle$, then the number of revolutions that the Quantum Fourier Transform makes is $j$. I.e., if we consider the initial state $|3\rangle$, then we obtain the following image under the Fourier transform:

Here, we can easily see that the helix completes $3$ full revolutions if we were to add one more circle on the right hand side.

It is important to note that we can also reverse the order of things. That is to say, if we have a quantum computer, whose state can be pictured as a helix, similar to the ones shown above, then we can obtain the period of this helix by implementing the inverse Quantum Fourier Transform. In doing so, we essentially map the helix with $j$ revolutions to the state $|j\rangle$, which is the exact opposite direction from the mapping we considered before.

It is this idea that is the crucial component in Shor's algortihm. The central idea is to take the sequence of numbers you describe:

7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)


and use these to create a helix whose period is equal to the period in this sequence. Next, we apply the inverse Quantum Fourier Transform to obtain the state $|4\rangle$, i.e., the period of this sequence.

NOTE 1: There are a lot of details that I skipped over in the final paragraph. This answer already contains a lot of information, though, which I think needs to sink in before one can attempt to add these details to the picture. If anyone wants me to add these details, I might do so at a later stage.

NOTE 2: The OP mentioned that he is not a mathematician. To the mathematicians out there, this visual representation is just an array of $2^n$ unit circles in the complex plane, where the marked points are the representation of the amplitudes as vectors in the complex plane.

• Thanks for the answer, I understand what you are saying, this is consistent of what I knew about Fourier Transformations (and the inverse). I guess the stories about clocks and magnutides confused me more than it should have. I'm going to take this different approach for explaining Shor! – Roy van Rijn Jul 9 '18 at 11:58

In your example the pattern is made by a modular multiplication function or circuit f(x) = ax (mod N) This quantum circuit and pattern is also given in the IBM Q manual of the IBM Q Experience.

So in a loop with start input x = 1

x=1 f(x) = 7 * 1 (mod 15) = 7

x=7 f(x) = 7 * 7 (mod 15) = 4

x=4 => 13

x=13 =>1

The pattern 1 7 4 13 1 is repeated every 4th time. So the circuit is fixed for a given a and mod 15 and always returns r = 4. If you want r = 2, you need another multiplier function