As I just said this goes here and we get this. Now, this expression maybe doesn't look more attractive than the initial one. But let us go further and they're going to extract the most significant qubit of this y. So this y, these qubits. I'm going to split the sum by the value of this most significant qubit, y_n minus 1. Okay. This qubit y of bit y_n minus 1 might equal to 0 or to 1. So first, let it be zero. I'll take also 1 divided by the square root of 2 from this coefficient and I get this e to 2Pii multiply it by 0. Since we agreed that first we consider y_n minus 1 equal to 0, and x_0 divided by 2 and the qubit_0 here, and then the remainder of our sum, 2 n minus 1 divided by 2, sum over all y's from 0 to 2 n minus 1 minus 1. This part goes here, plus 1 divided by square root of 2. Now, we consider this situation when this bit y_n minus 1 equals to 1. We have e in the power 2Pii multiplied by 1 x_0 divided by 2. Here we have zero, and here we have one. Again, 1 divided by 2 and power n minus 1 divided by 2, sum or the same minus 1 minus 1, and this goes also here. We are going to now accumulate everything from these sums. So we are going to make it like this. 1 divided by square root of 2. Here we have e in the power zero, so it's one, and we have just zero plus here we have e into the power 2Pii x_0 divided by 2. So let's write it down, one and this sum. E in the power 2Pii y_n minus 2, etc., and y_n minus 2, etc., y_0. So we have successfully extracted the most significant qubit out of this sum into this scope. Now, this looks promising and we might continue to do this with all other bits of y, and in this case, we will get these. Behold, instead of this enormous matrix with this number of multiplications inside of it, we have only n small operators, one qubit operators because each of these operators is one qubit gate, and we have only these number or these gates, which implement the QFT transform. QFT operator. This is maybe the most significant part of the Shor's result or the Shor's algorithm that this matrix can be represented as a tensor product of this smaller of just one qubit gates. Now these operators, these simple gates on which QFT falls apart in tensor product, they look a little bit unfamiliar to us. To implement them, we are going to need this set of this phase rotations operators. By set I mean that you will need the physical implementation of each such operator for k from one to number of qubits. To see how this operator works, we can apply it to the vector. Qubit_0 which is this qubit, and we can see that this qubit is it stays untouched by this operator. Now, let's apply it to our qubit_1, which is this vector, and you can see that this vector is multiplied by this constant here, e in the power 2Pii 1 divided by 2 in the power k and this vector. Okay. So this operator doesn't touch vector zero, and it multiplies one by this constant. It is exactly what we need to implement, all these operators, all these great n gates we're seeing here. So let's see how it works on an example is QFT and three qubits. So here we have this decomposition of QFT on quantum gates, and here we have the example of the circuit scheme for three qubits for QFT and three qubits. Let's check it line by line. So the most significant qubit, it is here and we see it here, the y2. If you take a zero and apply at the map transform x_0, then if x_0 equals to zero, x_0 is mapped by the map transform to this. If x_0 it goes to zero here, we have also this zero plus one and one and the map transform maps one to this, to the vector minus. You see that if you have x_0 equal to 1, you will have this exponent here which equals to minus 1, and we will have this 0 minus 1. So, if you apply at the map transform to keep it zero, you get exactly this scope. This is why we have here at the map transform and we get from x_0, we get the most significant qubit of the result. So you may note that QFT implemented like this, it reverses the qubit order from the least significant qubit, it maps to the most significant qubit. We are ready to proceed to the line two. So line two we have x_1 mapped by other map transform to this. We have this rotation R2, which does not touch vector zero as we remember. So we have this 1 divided by square root of 2, zero stays untouched plus and R2 here depends on qubit x_0. This exponent stays, 2Pii x_1 divided by 2. If x_0 equals to 1, we have this exponent introduced by this operator R2. So replace here x_0 if it equals to 1, then we have this exponent if it equals to zero, then if it doesn't have these exponents and the power here becomes zero, this exponent becomes just one. Okay. We have this scope here, and you may see that it is exactly the same as this. So this line in the circuits here represents exactly this gate. Here's a set line. You can check this as an exercise. Now, you see that we can implement QFT, we can implement it officially with just n operators which of which use up to n different primitive simple gates. So the complexity of the QFT transform of your QFT operator is this. Well, the implementation of QFT is ready, and now we can proceed to the implementation of Shor's algorithm in the next two lectures.