The important class of Quantum Algorithm contains the applications of Quantum Fourier Transformation. This is a main technique used in Shor's prime number factorization algorithm and they're the main part is the phase estimation. Phase estimation is connected to the order finding algorithm. This is the main technique used in the shortest algorithms. Here I want to show you how this Quantum Fourier Transform works in phase estimation and then as a simple example, we can see this phase estimation in the Deutsch algorithm test run. Quantum Fourier Transform works like this, it is n qubit state, so zero, this is to say is j_1 and etc., and we have j_n, so this qubit state. This n qubit state is transformed to this factor, new basis, by a Quantum Fourier Transformation. We can introduce the inverse Quantum Fourier Transformation bar, and this goes back to this guy. Then if we apply the Quantum Fourier Transformation in general, a vector which is spanned by this j, then we have the objecting one in here, and if you see the relation between these two guys and this precisely corresponds to the fast Fourier transform. We can see some examples here. For instance, if we see this one and apply the QFT and Quantum Fourier Transformation over n qubit, then the state we have here is this guy. We have n minus 1 and to the end. We have k element here, but our j is 0, so j and then k. This corresponds to uniform superposition of all vectors. This is by QFT, and the other way around is inverse QFT. Then if we have in general, we have the j, this guy, and then here k and k. Then by inverse Quantum Fourier Transformation, we recover this value. Now you can catch the point. If we start with a state, for instance, this one and have general some angle Phi and k and k. Apply just a Quantum Fourier Transform inverse. Then, something you can have is this guy up to n-bit. If we have some phase vector here, we can get as a bit values by inverse Quantum Fourier Transformation. Then we can construct a quantum circuit. The first circuit is to prepare, initialize, this guy. This can be obtained by say, we have our initial state here. Say, we first have to apply a Quantum Fourier Transformation, so QFT. Then we have equal superposition that we need a process that include this guy. This is called the modular exponentiation. We include a step that here we needed some step to include this guy, and for that purpose, we needed some operation u, then we prepare u. What is these two guys? They are related in the following way. If you apply u, then we have a phase vector i Phi and u. U is again one of the eigenvector, and this is the one of the eigenvalues of this unitary transformation. The process we include the phase vector here using these u and by control, and this is called a modular exponentiation. By doing that, we have include this phase factor in here. In the end, these Quantum Fourier Transformation and modular exponentiation, this prepare this state. The next step is to apply inverse Quantum Fourier Transformation. Then what happen here is this guy here, i Phi_1 and i Phi_2 and here. I wrote tilde here because this procedure is up to n qubit. In this way, this guy can be estimated by performing measurement. This may be some irrational number, then we need a many qubit, and as we increase the number of qubit, this will increase the precision. That's the process of estimating the exponent value here. Again, this is a key technique used in prime number factorization algorithm. This can be easily seen in the Deutsch algorithm as well, because this is somehow hidden in this picture. Here the Deutsch algorithm we apply the control u operation or i operation depending on the property of functions. I wrote hear u. The identity is either plus plus and minus minus, and x is plus plus and minus and minus. If the function is constant, then this u must be Identity. If the function is this unitary transformation here must be an x option to construct the scene overall. In both cases, we can see that the eigenstates is actually minus. Therefore the eigenstate we have two post-phase effector, which is this guy and this guy. Then we have a phase factor minus 1 and the quantity we wanted to have here is actually 0 plus 1. How can you relate these two pictures? I think we can map the picture for instance, like this. What would happen to this point? We have minus state. Applying x to 0, then H to 1, so zero is mapped to one and then Hadamard transformation transform one to minus. This is a minus state and that is the eigenstate of this guy. Both cases is u is identity. Then we have a face vector plus 1, and then if u is x, then we have phase effector minus 1. What we wanted to estimate this actually this value and that was the goal of the Deutsch algorithm. Then to estimate this guy, we have to perform inverse quantum fourier transformation which is Hadamard transformation, the case of single qubit. For single qubit, we have applied Hadamard transformation, which is actually inverse quantum fourier transformation. This guy is just a quantum fourier transformation. We have a quantum fourier, here and here, and inverse quantum fourier transformation and inverse quantum fourier transformation. Then what happened is that we can estimate exactly this guy. We can estimate here by performing measurement to make a more precise the quantity we have here, I mean, we can reduce this guy for single qubit case. Since a single qubit is n is 2. We have a single qubit which is n equal 1, and then pick n is 2 to the 1, then this two here. Then we have two and then zero, n is 2 and therefore high pi the angle phi n_1. Then if you perform inverse quantum fourier transformation, what you estimate is, in fact, this guy. We can relate these two guys, e^ i Pi phi. This is precisely minus 1 and phi. Therefore, we will estimate phi, which is inverse Fourier transformation or the Hadamard transformation here. In fact, we can put inverse with a stagger butt is identical to Hadamard transformation. This one is the quantity we have estimate here, and this precisely the number we were looking for in the case of Deutsch problem. Phase estimation has been used as a key technique in polynomial factorization. But this is somehow a hidden or often the usual technique we can implement or device quantum algorithm. This started from the beginning, actually the first quantum algorithm , the Deutsch algorithm. Deutsch algorithm here this can be interpreted as first computing or the algorithm for deciding if the function is constant or balanced, where we can see clearly the quantum advantages. Also this can be seen as a discrimination between two unitary transformations. This can be seen as an information task. Finally, we cannot see this Deutsch algorithm as a phase estimation. We implemented the unitary transformation and we have a eigenstates, this guy and this generate the phase effector depending on the property of function. If the function is constant, then we have this phase. If the function is balanced function then it generate this phase factor. In the end we have this quantity and this will be estimated here using this technique and this technique is called phage estimation.
