Okay. We've just learnt the algorithm which allows us to perform the search for the special points of function, implemented this as an oracle. This algorithm performs much better than the classical search. So, instead of 0 big of N big iterations it requires Pi divided by 4 square root of N iterations. So, we have a quadratic speedup, I understand this is good but is this good enough? Intractable problems like travelling, salesman problem, still remain intractable. It need more speedup. The question is, can we design a better algorithm? Some big operator U reach performs better than Grover which will provide us with for example, exponential speed up. Lov Grover in his paper where with the description of the algorithm proved that we can't. To understand the proof, we are going to need some new notations. Omega. We already know this. This is a special point for the classical oracle and special vector for the quantum oracle. By U here we will denote the algorithm in a very general way which should believe performs better than Grover's. Here you see the queries to the oracle and between the squares there are some operators which in Grover's case o equal to u s. But here since the algorithm is a very general, we might expect them to be different. Psi zero is our initial state. So it's substitute of the vector S and Psi T is the state of the system after t query. After t iterations that means the and t query to the quantum oracle. T is the number of iterations needed for the algorithm to perform to obtain some vector which is very close to Omega. So, we could obtain it after the measurement. So this is vector Psi Omega. The vector Psi Omega is the vector the state of this system after t iterations and it must be close to Omega. Again, by N big, we will denote the dimensionality of our state space which is 2 and the power n. The idea proof is here. We're going to find some vector Phi for which this double inequality is true. On the left here you can see an expression which depends on the number of iterations of our most effective algorithm t. On the right we see the expression which depends on the dimensionality of the space hence the possible number of oracle inputs. You may notice that both these expressions do not depend on this vector Phi. So, if we find such Phi for which this inequality is true, then this smaller inequality which consists of only the left and the right parts here holds always. Which would mean that for the most effective algorithm the number of oracle queries must be something like square root of n divided by square root of 2. For Grover's case we had, as you remember Pi by divided by a 4 square root of N. So the most effective algorithm is not very much better than that of Grover. We start with the right side. So first, let's note that for different special points of an oracle like Omega i and Omega j. So, different oracles our most effective algorithm converges to the different vectors or the state space. Since the algorithm is so effective, this vectors to which it converges must be close to the points of interest. These points if they're different they are orthogonal. So, this vector, the final states of algorithm for different oracles must be nearly orthogonal. From here on We'll say that they are not freely orthogonal but just orthogonal. They are N big different special points. So, there are N big of this vector Psi Omega. Since they are orthogonal they form the orthonormal basis in our state space. Now with this, let's take a closer look at this middle part of double inequality. We have this big sum here and sum squared difference. So, let us decompose the squared difference. It will have the sum over O Omega Psi Omega squared plus some Omega Phi squared and minus sum over O Omega c Omega Phi. Instead of two sums here as an Euclid space it will have two different sums because that product is not symmetric like this. We remember them that for different Omegas we have this Psi Omega elements of orthonormal basis. So, we can represent the vector Phi in this basis. Let's do it. So, Phi equals to sum of x1, x2 et cetera xN big. These are the coordinates of the vector Phi and these vices Psi Omega. It shall this coordinates is a complex number. So, it has real and imaginary part. Which we'll denote like this aj and bj. Now we can put everything I just introduced here. We're know just that these are unitary vectors. So these are ones. So, we have 2N once and minus this sum since these are the products of a vector on the basis vector and in this basis we have this representation. So, it's sum over j equal to 1 to N x j plus x j conjugate it. This is just doubled real part. So, we have 2N minus 2 sum over all j from one to N a j.