Quantum computing, Computing, Quantum mechanics, Quantum algorithm Fourier Transform by MSc student Maria Flors Mor Ruiz
The quantum fourier transform, also known as qft like the classical fourier transform, takes the data from the original signal representation to the frequency domain representation. The difference between them is that the quantum one operates in a superposition state and thus produces a different superposition state. As the output quantum fourier transform is based on using interference as the components of the superposition which can interfere either constructively or destructively depending on their amplitude and phase. First, we shall develop the math behind the quantum fourier transform. We can say that the quantum fourier transform applies as a unitary gate. U q of t, then for a general state of n qubits. It is applied in such a way that we are left with. A superposition of states saw in of the same weight with different phases. Earlier we said that the quantum reactions form can be seen as a unitary gate. This is done by showing that the qft can be decomposed as a product of unitary gates, which consist of hardener gates, rotations of different angles and swap gates. Importantly, a product of unitary gates is a unitary gate. For example, let’s examine what happens in a two qubit system. This q of t has the following circuit representation. Adding more cubits involves the product of more and more of such unitary gates. Now we want to observe the effect of the q of t to do so. We will show an example using a two qubit system.
We can write the possible states using a two qubit system in three ways. With the bracket notation, we can either use decimal or binary and we can also use vector representation. First, we will apply q of t on the zero one state following the formula that we have presented previously, we get the following result. Alternatively, we can represent the q of t on the state as the phase rotations to the qubit. The q of t gives a different phase to each state. The pattern goes as follows. The qubits in the first position, starts put in the second position. We rotate the cubits a quarter generally one over n. Where n is the total amount of positions our qubits can be in in the third position we rotate by two over four or half? Finally, in the last position, we rotate by three over four or minus one over four. We will now apply the q of t to all of the states in our two qubit system. We get the following results, which together represent the quantum fourier transform. Let’S say we want to apply the q of t to a superposition of states. In our example, note that applying q of t to a superposition is the same as applying q of t to each of the states in the superposition and then adding the different q of ts. In this way, we see that the different q of ts always either destructively or constructively interfere.
Importantly, the points where we get constructive interference come at a certain frequency. F remember this is a fourier transform. We move into the frequency space here. In the example, we see that we get destructive interference in the second and fourth position and we get constructive interference in the first and third position. After this. Summing all the qft outputs of the initial superposition, we see that the constructive interference occurs with a frequency f. Where do we go from here? Let us take short algorithm as an example. Now that we have our frequency, we must realize that the period we are searching for in short, algorithms is p, equals 1 over f. Now that we have our period, we are one step closer to solving for our prime factor in general. We can see that this tool can be useful for many algorithms in quantum computers, as we’ve seen, schwarz algorithm is based on period finding, which is exactly what q of t does.