Hello everyone. Welcome to the third week of the course. In this modular, the final descent from obstructions to the solid ground and discover some algorithms. We start with the first algorithm ever designed for a quantum computer, the algorithm for solving Deutsch's Problem. Actually this first algorithm presented by David Deutsch in 1985 was not the main topic of his paper. The main topic was the mathematical model of quantum compution, which we learned on the previous week. The algorithm was just an illustration for this mathematical model. So, thanks to this man, you now have this good mathematical abstraction which allows us to design quantum algorithms without any extensive knowledge in quantum mechanics. I placed here on this slide some colors of his popular books and in fact has more, but these two very popular here in Russia and they are the only I have read so I can personally recommend them and so I do. Here is the plan of our third week and we start as you may have noticed, is Deutsch's problem. Then we are going to make a quantum computer with our own hands. This quantum computer you can see on the picture here and then we are going to solve the Deutsch problem on this real quantum computer. After that we will learn some basic algorithms. So, let's start learning. Deustch problem is about the function which maps one bit to one bit and there are only four such functions. We can easily name them. So, f of x equals zero and f of x equals one. These two are constants and the bonds that functions which have the equal amount of ones and zeros and the image. This f of x equals x and f of x equals to not x. We call them balanced. The function itself is implemented as a black box. This metaphor means that we can't see how the function is implemented. We don't know how it works, we only can query it as an oracle. So, again, give it an input input one or zero and read the output. So, it's black box here. Unluckily for us, this particular black boxes very slow. One query takes 24 hours. The question is, which type of the function seats here in the box? Is it a constant or is it a balanced function? So, how much time do we need to answer this question? In classical case, it appears that we still have to query this oracle twice to give it zero and one and to see what it returns. After that we will know exactly which of these functions sits there. This is users information for us. We need it on the type and we'll put bait for this user's information with our time, with extra hours. In classical case, there is no hope to solve this problem faster, but in the quantum case we have an algorithm which doesn't. As we learnt before, all quantum operations are performed by unitary operators and quantum data is represented to us by vectors in a Hilbert space and we have a function which maps one bit to one bit here. So, we might expect for a quantum substitutes for this function, we will call it Uf. You might expect that it maps one cubit to one cubit. For example like this. Is it fine? No, because if function f is a constant zero for example, then this operator glues together different by this vector, so it will map zero to zero and it will map one to zero. Thus it is not unitary. So, this operator doesn't work for us, it's not to unitary and to fix this we need to add some extra cubits like this. We add this second extra cubit and we map it like this. Okay. Now, these two vectors zero, zero and one zero are not glued together because they still map two different vectors. It seems like they solved the problem but not completely because this unitary operator Uf must be defined on the wall space, that means on all basis vectors. So, we need to define how it works on these states. We can define it like this to distinguish these vectors from these vectors and the operator defined like this, maps orthonormal basis to orthonormal basis, so let it be the definition of our quantum oracle which works like this. This plus here it is an x0 operation. Having quantum oracle defined like this we obtain another useful and interesting feature. If we apply our oracle to these type of states where in the last cubit we have this adaman minus, let's see what we can get. So, this operator is linear and we can write like this x0 minus Ux1. Now, let us recall how this operator works. U(x)f(x) minus U(x) one plus f of x. No you hear anymore. Now, if f of x equals to zero, we have x0 minus x1 which is our initial state, X0 minus one. If f of x equals to one, then we have x1 minus zero. So, it is minus our initial state and we can write it like this. So, you can see that this operator Uf on this state doesn't really change the state. From the S this coefficient here minus one if f of x equals to one.