QUANTUM COMPUTING: QUANTUM FOURIER TRANSFORM [PART 2]

Let's keep developing some reasoning from where the previous article [QUANTUM FOURIER TRANSFORM PART 1] was interrupted.

The initial problem we aimed at resolving was to express the QFT only in function of the input qubits (i.e x). This is predicated on the notion that to extract useful constraints from any abstract result and build useful representations which then can be translated into usable models, input and outputs shall be separable.

Somehow we derived the expression of the QFT as Tensor product, over n qubits , on a n-dimensional Hilbert Space [let's recall that a unidimensional Hilbert space represents a qubit, therefore for n qubits, we need to refer to an n-dimensional space].

Let's recall the equation:

Let's briefly develop the Tensor product over n-qubits:

Let's focus on the n-th qubit and ask the following question:

What is that the term x/2**n represent?

We already came to the conclusion in the previous article that x is a decimal.

What we want to understand is how x (decimal) relates to its respective binary value since the result we are looking for must be binary (unless the qubits are in superposition or entangled .... but this is another problem which we will treat in future articles. Let's keep it simple for now....)

Let's express x/2**n as follows:

Let's make an example to clarify:

n =3 (3 qubit) and x = 5 (101 being its expression in binary)

5 / 2 **3 = 1/2 + 0/2**2 + 1/2**3 = 1/2 + 1/8 = 5/8 = 5/2**3

So to express the decimal in bit format we consider 5 in binary (101) and move of a number of positions equal to n=3 from right to left:

5/2**3 = 0. 101

We can use the same reasoning of FIGURE 3 for n-1 for example:

In the final analysis, if we consider the exponential (the phase basically) we have that (i am omitting some passage that uses Eulero's Formula if you do not understand it please let me know):

Let's make an example (same n=3 and x = 5/2**3) to put emphasis on how the value of n is correlated to a phase rotation (given by the exponential)

Let's re-write the QFT equation using the binary expression (reference FIGURE 2):

Let's close this article by developing some intuition on how quantum computational gates can be derived from equation of FIGURE 2:

The tensor products are executed between qubits, therefore if we consider the first qubit, we can come to the conclusion that it represents the QFT of the first input.

The gate that make the transformation is called Hadamard gate and is represented as H

I will introduce the quantum gates in another article with the Bloch sphere and the Pauli's group and explain their significance (normally they are done before the QFT, but I prefer to do it later as going backward it is easier to develop intuitive thinking).

Anyways, in the case of the second qubit, the phase of |0> remains the same and the phase of | 1 > is changed to exp(2Pi i x/2**2) and for the 3rd qubit the phase of | 1> changes again of a factor 3.

Intuitively we understand that the phase of 1 Rotates. To Create a representation, what we need is then a rotational operator or Matrix which can change only the phase of | 1 >. This Operator will be the Matrix R.

Next article, when time and will allows, I will try to describe in simple terms how these operators / Matrixes are constructed and what their function is.