Let's take a brief look at some other quantum algorithms designed to show the power of quantum computing. The Deutsch-Jozsa problem published in 1992 is formulated like this. You have a black box oracle function which maps n beats to one bit. We know for sure from a reliable source that this function is either a constant or bound set. Bound set function is such function that returns equal amounts of ones and zeros. So, the question is the same as in Deutsch's problem, which case of these do we have? Is this oracle function a constant? Or it is a bound set function? Now, if we don't need a 100 percent certainty, then classically, this problem is not extremely hard. Because if we call this oracle for example, 10 times with random inputs and each time we have the same value, then we can bet that it is a constant and the probability of mistake would be this. But if you need 100 percent certainty, then a constant in a black box becomes a nightmare because we have to check this number of inputs to be sure that this function is constant. But for the quantum case, the things are much brighter. To solve this problem, we will need almost exactly the same circuits scheme as in Deutsch's case, except for one thing. We now have n cubits in the x register here, and we have to apply the n cubit at a Hadamard transforms here and here. So, let's root. We have this state and then we apply n plus one cubit Hadamard transform which gives us n plus one divided by two here. Remember, this formula that we have proved and the previous that you proved on the previous week for the Hadamard transform and to use it and we do, x from zero to two and minus 1x and one transforms to this. Okay, now it's time to apply our quantum oracle, and on the states like this, you remember how it that's on the state's with Hadamard minus in the last cubit. So, again we have this and the sum over all vectors of the space. Now, minus one f of x, and this minus vector here. We are now going to take a close look at this state here which you have to apply Hadamard transform to. So, let us concentrate on this x register now because only it will have to modify and measure from this point. So, we can forget about this and about this. Now, imagine that the function f of x is a constant. Then this minus one is going to be always on the same power, and we can put it out of the sum here. The sum transforms to something like this. Minus one here and this function later. Now, this sum is very familiar to us. We just have seen on the previous slide. This is just the model and cubit of the model of n zero's vector. Okay, you can write it like this. So, after Hadamard and measurement, we will get this vector which consists of all zeros, of n zeros. Okay, now, if function f is not a constant, this bound set then we have two types of coefficients here in this room. We can split this sum like this. So, by the value of the function, and since this minus one here, if the function f is one equals to minus one, you have to put this minus here, and of course, the coefficient here. Now let us recall the formula for the Hadamard transform. This is our formula for Hadamard transform. Now, imagine this vector y is o zeros. Then this thick y and product here is zero. This vector is always with a coefficient plus one. So, for any vector x, if we had applied Hadamard transform to it, it will be the sum of all basis vector. Vector of space, but these vector with zeros will be always be the coefficient plus one. We have legal amounts of theorems and these and these sum because the function is balanced. We remember that this sets have the same number of elements. So, here we will have this number of these vectors of all zeros. Here we will have the same number of these vectors but with minus, and these vectors will self destruct. Then in the output, there will be no vector of all zeros and if you measure the result, we will obtain any other vector except this one. So, only after one application query to the quantum oracle, we can distinguish bound set and constant functions. Because for all constant function, we will get exactly this vector as a measurement result. For a bound set function, we don't get any other vector. This self destruction of vectors here reminds me of interference, it is actually, it is an interference Bernstein-Vazirani Problem, 1993. Again, the function maps and beats to one-bit. We know that the function is implemented like this. So, it is like a dot-product and is that true. Well, we know this much, but we don't know this number a, and we want to know it. Again, the function sits in the black box so we can't look inside. We can just query this oracle, feed it some inputs and see the outputs. Classically problem is not that hard. They can feed the inputs like this with one once in only one place to obtain different bits of this a. So, since a is n bit, we'll need n oracle queries in the classical case. But we already got used to solve the problems in just one Oracle query. So, we proceed to the quantum case, and the quantum algorithm is the same as for the Deutsch-Jozsa Problem. Since it is the same, and acts the same, so up to this point here, we have the same value and the input. They are all registered in the system state. The function f here is a thick buoyant x. If you look at this expression here, you may notice that it is exactly Hadamard transform of a. So, after this Hadamard transform and as a result of measurement, we will get the value of a in just one oracle query.
