Up to this moment, we considered the problems on which quantum computers perform significantly better than classical ones. Now, this may have a look of unfair advertising. Because you may believe that quantum computers are always better. Unfortunately, this is not the case. In this lecture, we will examine the problem on which the quantum computers are almost as ineffective as classical ones. Let's consider all the functions of this type which map and bit integers to one bit. Then for any such function, we can introduce this video. This is actually a very long bit of strings, string of bits and big bits which is ten to power and small here. For any index here xj equals to the value of function on this value j, and j runs from 0 to n minus one. So, this is how very long string of bits. We introduce a quantum oracle as we do always. We do this sign ways always. For example, if we put some index j here, f of j y, it will be j y one, and this means that f of j equals to one so we can put x j here which is 1 plus 1 minus xj, again j and y. So, if xj equals to 1, then we have this part here and this goes to 0. If xj equals to 0, then this part stays and this goes away. Now, we can notice that if we apply the oracle uf t times, then any of these states, any of these basis vectors will have a polynom, polynom of power t of this xj's for these different indices before each state vector. Now, let's introduce the following notation, xy wave, 1 minus 2 xy, xi. Let's consider such function parity which maps functions to one bit. So it accepts the parameter. This nb string, zero, etc is long string of function values and it computes the product and it returns one if among these values there are even number of ones and in other case it returns minus one. So, the question is, if we have function which maps n with integers to one bit, and this function is implemented as an oracle, as a black box. How much would it cost us to compute the its parity? In classical case, the answer is obvious, we have to try all the function values. We have to compute all the function values then multiply them. Maybe the classical complexity is not even 0 big of N but just N, N big. Maybe with a quantum like box we can do better. Let's see. So, we have the quantum oracle and we have designed some algorithm which is effective and it gives us an answer if the oracle function is even or not. In t queries through this oracle, quantum oracle. Let t be less than and divided by two. So, it is at least twice as effective as the classical algorithm. So, after t queries to the oracle, each state would have a coefficient, a polynom of the power t of this x. If we measure this result then the probability of measurement will be the polynom of power 2T because we square each coefficient before the state if we want to compute the probability. Now, some of these states are markers that the function is even for us. So, if you measure these states, we say that the function is even and the sum of all these probabilities of these markers we will call b even. If it is a polynom of a power of 2T. So, it is the probability for us to say that the function is even and it depends on the function of course. Now, let's consider this expression. We take this probability of the answer that the function is even, multiplied by the real parity of the function, and we take the sum over all possible functions. Let's split this sum by some random index. This sum is over all the functions for which xj equals to one, and the coefficient before this sum is one and the sum over all functions for which the j equals to minus one. Again, P e et cetera, product over i not equal to j, x i. We have this minus before this sum because we removed this index from here and this index gives us the minus. Let's look at the sum. So, the polynoms here of the power 2T which is less than n. So, we can choose this index j here. For any monom in these polynoms we can choose this index j such as, it is not contained it in these monoms. In this case these sums become equal, and since we can do it for any monom since the power of the polynom is less than N, and we have N big of possible indexes. All the sum appears to be zero. Now, we already know that the sum is zero. Let's split it another way. Let's split it by even and not even functions. So, this x such as x is even, and we have this polynom here and this product for even functions is one. Sum over x which is say odd. Again, this same polynom and this product for odd functions is minus one. So, we minus here and we see now that the probability for us to say that a function is even equals to probability for us to say that the function is odd if 2T is less than N. So, we can't be sure, we can't say anything concrete above this function if we make this number of iterations. Which means that Quantum Computers cannot outperform classical ones on this task, cannot outperform in this case they cannot perform twice better. Twice as good as the classical algorithms. With this optimistic result, we finish our course, the introduction to Qantum Computer. This was tough and long still I hope enjoyable road. Thank you all for your attention and participation. The course team wishes you luck in your further research and study and welcomes you to the other courses of Saint Petersburg State University. Goodbye.