[MUSIC] Limitation of Charles algorithm request the new we never meant before in this course. Quantum Fourier Transform the QFT, the definition of this operator you see here on the slide and for those of you who are familiar with signal processing I bet this expression look familiar. And from now on we are going to use these notation. So big N is now 2 in the power small n, where n, and small is number of qubit. And as always we start with a check, we check if I did not by introducing some operator which is not unitary so we have to check the unitarity of QFT. And we start with a norm, we are going to check if QFT preserves norm so we have this square norm here, of some vector x and we go into, See what it, across 2. So we have this square root I want to fix here and 2 and power n here and big dot product of 2 sums or y's or this sum from zero to and about m minus 1. On the first place e minus 2pi, x, y, divided by y. And on the second place the sum is plus Plus 2pi, x, y, and y. And of course, this y, this counter sub difference. So this y1 and y2 here. Okay, now we are going to split the sum this way. In the first place, we're going to place the sum over different ways y1 does not take off to y2. We have some exponents and that product of y1, y2. Which is zero because y1 and y2 are different greatest factors. So this part is zero plus the sum over equals e minus 2pi is y1 divided by N. And since y2 equals to y long we can write [INAUDIBLE] 2pi is y1 again, divided by N, multiplied by y1, y1. Okay, this obviously, equals to 1 and this is the same versus vector also equals to 1. Okay, and the number of terms in this one is exactly 2 and the power n, which is N big. So we have 2 and the power n of ones. And the total sum multiply by this is exactly x square. So check past and QFT preserves to norm and let's see what the that angles. Okay, let's see if QFT preserves angles. We know it preserves the norm. So instead of the norm here, we can write just one since we work only with unit vectors in our spaces. And we have two different basis vectors here. Octagonal vectors x1 and x2. And we apply QFT to that and we see what happens to the dot product. Okay, we have 1 divided by 2 and the power n and again dot product of the sums. Over y1 and y2, and we already know that for different y1 and y2, to dot product is zero, so we recognize that by writing this, All are the same, y1 sum all this and y, e and a power -2pi x1y divided by n, e 2pi, x to y divided by n and the product of y over y which is 1. So we have finally we have this sum. Okay, now many of you probably expect, Predict that the sum goes to 0, but some of you might not know why. And there are two ways to prove this. The first way is that the sum is the sum of all roots of unity, of the power n and this kind of sum always equals to zero. And the second way is to prove the first statement I just said by using this formula of the sum of genetical progression. Genetic progression, so let's apply the formula and see what happens to this sum. They have again this one. Divided by two in the power 0 and if I take y here is 2 and then. Is going to self destruct, and we will have a operator e to the power 2pi, xy, x2 minus x1 minus 1 and denominator it will be just e to 2pi, again x2 minus x1. And 1 divided by N big minus 1. So this does not equal to 0, and this does because here we have some integer, and the exponent, complex exponent with Integer number or this and those to 2p always equals to 1, so we have 1 minus 1 and all the sum equals to zero. That we see that QFT reserves not only norm but angles to. Thus it is unitary, okay, everything is fine with QFT. And now we have to know, how much would it cost us to implement it? First, we can see that this part here can be simplified since the integer number of this 2pi's in the power of exponent gives us 1, so we can keep under the fractional part of this fraction. Okay, now we are going to decompose this fractional part. That's why model of N divided by N and to this we are going to need the bit representations of both these intergers x and y. So let's write xy, x0 plus x1 multiplied by 2 plus x2 multiplied 4 plus etc, and plus xn minus 1 multiplied by 2 and power n minus 1. Okay, and the same for y. y equals yn minus 1 multiplied by 2 and n minus 1. Our etcetera plus y1 multiplied by 2 plus y0. So if we multiply x and y multiply these bit representations. So these sums and when we multiply two sums, we actually multiply each member, each term of the first sum with each term of the second sum. But if we multiply for example this term by this term we will get the power of 2 equals to n here so it will be yn minus 1, x1, 2 in the power of n. And when we divided by n, we just 2 in the power n, we get integer. So we don't get the fractional part but we need the fractional part. So we remove all such elements from this product. And, The thing that stays and this product is, yn minus 1, multiplied by x0, divided by 2, plus y minus 2 multiplied by x0 divided by 4 plus x1 divided by 2 etcetera, y0, x0 divided by 2 in the power of n plus x1 divided by 2 power 10 minus one extra. So x and minus 1 divided 2. Okay, and now all of these. Goes here, in this power of exponent.
