As you already know, there is plenty of quantum operators which map one cubit to one cubit. There's actually an infinity of such operators, but there are only four functions which map one bit to one bit and we are going to implement their quantum operators for each of these functions. We'll start with a constant f of x equals to 0. Now, the operator for this function acts like this. This f of x equals to zero. So, it's just xy for any vector. So, your f in this case is just an identity matrix, four by four, of course, because we have two cubits here. The implementation of such matrix on a circuit is quite simple. This is just nothing. Okay, we'll continue with constants. Let f of x be one, uf acts like this in this case. So, it always flips this lower cubit and this scheme is going to be this, follow this operator, and the matrix is this, which is y as a product x. Well, let's continue with the balanced functions, f of x equals x. Now, we are going to consider different vectors. Now, 00 maps to 00, 01 maps to, again, 01, 10. Now we have x equal to 1 and we add this one here, and we have 11. Of course, 11 maps to 10 and we perfectly know this operator. It is just CNOT. Even more fun with f of x equals to not x. Let's see, 00 not x is 1, it maps to 01, and 01 maps to 00. Now, 10 is untouched the same as 11. Those of you who did the exercises for last week perfectly know this operator. This is contra CNOT which is like the operator with this matrix, and the scheme of this operator is this, the circuit of this operator is this. Now, let's proceed to the algorithm. So, here's the circuit scheme of the Deutsch's algorithm. As you can see, we pass zero to the most significant cubit, to the argument cubit and to the value cubit, we pass one and then we apply Hadamard and only after that, we apply our quantum oracle, quantum black box in which sits one of these things here. But we don't know which one. So, in quantum case, before we query the oracle, we make some clearer preparations and we query the oracle only once. After that, we again apply Hadamard to the input register, and then we measure the input register, not the output. Looks a bit intricate, so let's see how it works. So, here is the scheme, let's apply it. Now, we have this 01, after Hadamard it would be 0 plus 1 at this vector plus and vector minus. We can write it like this. So, we are here now and at this time to apply the oracle. You remember that for this state, the oracle works like this. So, it's one-half minus 1 and power f 0, 0 minus plus one-half minus 1 f of 1, 1, and minus again. Well, now we're here, let's combine these values in the scope. So it's, again, one-half, that's minus 1 f 0, 0, plus minus 1 f of 1, 1, and here is this vector minus, which is not any more interesting to us. We are now interested in this first cubit because all the actions here are applied to it. Okay, imagine that f of x is a constant. Then this powers of minus one here are equal, f of 0 equals to f of 1 and we can put it away from this scope, and here we have just vector plus and after we apply Hadamard to it, it will be zero. If f of 0 does not equal to f of 1, which is true for any balanced function, then these powers are going to be different and we have here vector minus. After Hadamard it will be 1. So, for a constant function, we get zero in the input register and for a balanced function, we get one, so we can easily distinguish them. We still don't know which function stays here in this quantum black box. So, we don't get this extra information and we update the result in 24 hours because we query this oracle only once. On this slide, you can see the implementation of Deutsch's algorithm on a quantum computer simulator developed by my student, Yuri [inaudible] and you can see the Uf operator here is CNOT. So, its identity function f of x equals to x, and no surprise, we get 1 here. Actually, we don't need this Hadamard here. Now, this quantum simulator is available on the link http://qc-sim.appspot.com and you can find this link below the video. Now, what is the trick here? We have introduced something more complicated than a classical oracle. Classical oracle takes only one hit and this thing takes two cubits, and we pretend to solve the problem more effectively. At this point, it may look like this, but let's go further.