Okay, from now on, we are going to use these type of diagrams to describe quantum algorithms. The lines here denote qubits. The most significant is the highest. So, this state here is 0, 1, and on this lines we are going to place these squares, which will denote quantum gates in order to off the application from left to right. So, here we apply Hadamard gate to both qubits and you can see that we have two qubits here, so the whole transform. This transform must be a matrix four by four. What is the look of this matrix since the dimensionality of the space is four? It is easy to compute this matrix. You just need to multiply it H by H to compute the tensor product or Kronecker product, which is this tensor product and it is this matrix. Okay, it is generally true that if you have two different operators which are applied to do different qubits, then you can represent it like this Kronecker product of these operators, which is applied to the Kronecker product of the composite system of the qubits of the initial system. This identity can be easily proved, and I will leave you this as an exercise and just one small hint, how to prove this identity. This both sides of this identity are vectors. So, you can choose some index at random and to prove that for any random index, the component is this index in this vector equals to the component with the same index in this vector. Okay. What if you have this situation? The dimensionality of this space is still four, so the whole matrix here must be four by four. But we don't have anything here to compute this tensor product. Actually, if nothing happens here, then we can place an identity rather, here is, thus nothing. The matrix of this transform will be this. The very same situation here, the matrix will look like these, which is the square root of two. Identity, identity and minus identity. These are not operators. We are going to represent like this. So, this bit is controlled and this where we have this thick dot is the control bit. If you have this transform, for example, three qubits here. So, the dimensionality is eight and this matrix must be eight by eight. Again, we can easily compute it. So, it is this matrix. This are just parts four by four in this matrix. Okay, now a little bit more complicated question. What is the look of this matrix? Again, it is matrix eight by eight and there are only three possible ways of obtaining this matrix eight by eight by a tensor product. So, we have to multiply three matrices, two by two or one matrix, two by two, by four by four or maybe this way. So, we already have a matrix four by four which is CNOT and matrix two by two. Maybe this identity matrix two by two, but we don't have to put it from the left or from the right of this CNOT, we have to put it inside somewhere in the middle and there's no way we can do this. But maybe we can decompose this CNOT matrix on the tensor product of two smaller matrices A and B, each is two by two matrix. So, if we could do that, then we could represent this operator here like these. But, again, there's no way we can do this because matrix CNOT cannot be decomposed and the tensor product of two smaller matrices. It appears that this matrix, this gate CNOT, acts on both states, and we cannot implement it as an acting on separate states separately. So, there are no operators which can be applied separately to all states to obtain the action of this CNOT operator. We already met this situation with entangled states, where there was no separate state for different particles. This situation is quite the same. So, those states were entangled. This kind of operators like CNOT, they are entangling operators, and they are the main obstacle in grades and the physical implementation of quantum computer. This is the most complicated operators to implement. Okay. This is all good, but we don't still have the look of this matrix. Again, can we obtain this look? Yes, we can. Let's have a look how any matrix A here. So, this is some unknown matrix A. How this matrix acts on a bus vector, where we have only one, 1, which is on the position K. So, it's just a simple matrix multiplication, so we'll multiply each row by this column. The only index which survives in this row is index K. So, the result of this matrix multiplication is the Kth column of the matrix A. This is our hint how we can obtain the look of any unknown matrix if you know products on buses vectors. For example, we take our favorite vector 101, which has for each K is 6. So, it has 1 on the place 6. We know that the action of this operator is this. The control bit here is 1. This has to flip the last bit which is controlled. So, this state is transformed, is mapped by this separator to this state, which is the vector where we have 1 on the place 5. It would be 5 here for this vector. So, we can obtain the whole look of the matrix which is this. You can see that the sixth column here has 1 on a place 5. This is the column we have just computed. Okay, there remains only one thing that we need to go further. We are going to need this expression for the end qubit, Hadamard transform. Many algorithms which we will learn will start like this. There are many qubits. To reach these qubits at the start of the algorithm, we apply Hadamard transform. Since we're going to need the look of this matrix, instead of computing this enormous tensor product each time, we are going only once prove this expression. But let's take a look at this first. So, we can see that this transform here maps any input vector to a sum of all vectors of all buses vectors in our space, the dimensionality which is 2 in the power of n. So we have 2 in the power of n of buses vectors. They're all present here in this sum. Please note that this y here is a vector, and this y here is a number, some binary representation. So, here we count all the numbers from 0 to 2 in the power of n minus 1. Here we add up the vectors which are encoded by these numbers. The coefficients of this vectors are either plus or minus 1, and they depend on the input vector. Then sig dot product here is actually the inner product in this space. So, it's just for each component we have this multiplication, and then we add up all their results of this multiplication, all these bits, modular 2. Okay, how to prove this expression. I would like to prove it by induction, and actually I will leave it to you as an exercise, but I will help you with the base. So, for n equals to 1, you'll have H_1 of x, which is 1 divided by square root of 2, and the sum of y from 0 to 1 minus 1, x sig dot y. Y is just 1 divided by square root of 2 if y equals to 0. We have just this 0 vector because this sig dot product gives us 0. Then we are going to have this minus 1 in the power x and 1 here. So, if x equals to 0, we will have vector plus, and if x equals to 1, we will have vector minus. So, the base is okay. We have proved it. The induction step, I'm leaving you as an exercise. But if you don't really like this exercise, you can see this proof on the slides to this lecture. Okay. Now we have everything we need to continue and to learn some basic quantum algorithms and even to build our own quantum computer, which will implement one of these algorithms. This quantum computer is going to be, the qubit is there, will be recorded by the polarization of photons, not only the polarization of photons by photons. But this is our plan for the next week. This lecture is over. I hope to see you next time, and I wish you good luck with the week test. Goodbye.
