How do you get from this: to this:?

Welcome to the 5th article in my series on Quantum Computing.

In the last article we spent the majority of our time setting up Qiskit in PyCharm. We encountered a couple of hurdles along the way (like getting Qiskit to generate charts), but in the end we managed to get it all working – but didn’t really do any quantum programming. That’s about to change.

The problem is, we don’t have any tools to convert mathematical operations in to equivalent quantum circuits. I know we had a brief look at how this was done for addition on classical circuits, but did you know that even addition is forbidden in quantum circuits? More on that later.

Instead, we are going to look at a different mathematical operation known as a *fourier transform* and see if we can get it constructed in to a quantum circuit.

This will require quite a bit of math. But if you can get through it, I guarantee you will feel a lot better about this step in the process of quantum computing. In fact, I think this step in particular, separates those who *think* they know how quantum circuits work and those that *do. *

This article will involve a range of more advanced topics but, like before, I will introduce each one very slowly. If you are not comfortable with the tensor product representation of a many-qubit state basis vector, you will have to brush up on that. We will also need to be familiar with the Hadamard gate and the Rotation gates. We will be working in the Fourier-transformed *amplitude* space, so a lot of the calculations will be rotations in the complex plane – get ready for a lot of complex exponentials. There will also be a large component that needs to be converted in to binary (so that we can see exactly how each input qubit maps to an output qubit). For this we will be delving in to the realm of fractional binary notation.

Lastly, we will finish this article off by *theoretically* building a circuit – yes, we will be going all the way from the Fourier Transform *to an actual quantum circuit*. In the next article we will implement the circuit in Qiskit’s Aqua in Python.

## The Quantum Fourier Transform Circuit

What is the Quantum Fourier Transform (QFT)?

First, it is a linear transformation – which means that it preserves addition and multiplication by scalars; and that it can also be used in quantum circuits (all quantum operations *must be linear*).

But this is nothing special, many interesting maps are linear. So what else?

Well, it’s unitary. OK, that’s particularly useful for quantum programming, it means it has a Hermitian adjoint. It also has a matrix representation. Also cool. But what does it actually do?

It maps vectors to funny-looking vectors:

That looks ugly and there are a lot of letters in there to explain. First, it involves a summation over complex numbers; can be set to absolutely anything but trust me when I say that it is useful to set where is the dimension of the vector. We often use the abbreviation:

which is a rotation, and so the map looks like this:

and so it is clear that the QFT is rotating something around something.

What else can we do?

Well, we can use qubit notation for a *basis state* :

Note how replaces in the exponent.

Therefore, if we have a 3-qubit system, the QFT would map a basis vector like this:

and therefore, even though we only have 3 qubits, we will need an -matrix to describe what is happening term-by-term.

Let’s see what the matrix representation of this 3-qubit system looks like:

For the first row, the first entry would be:

The second entry would be:

In fact, every entry along the first row is 1 due to the presence of the zero in the exponent.

Moving on to the second row. The first element would be:

The second element on the second row:

The third element:

Continuing in this way, we arrive at the full matrix representation of the QFT:

This bulky matrix can be simplified using a bit of algebra. Note that since is an root of unity then for any if for some integer .

Since we are working with eighths (i.e. ) any time we see a , or indeed, any multiple of , like or , we can replace it with unity.

Furthermore, we can reduce rotations to *modulo 8*, i.e. if we see a , for example, we can write this as because ten is equal to 2 *modulo 8*.

The resulting matrix for QFT is:

This is what you would call a concrete example of a QFT matrix. What we need is an generalised version of this matrix that holds for *any number of qubits*. Only then will we be able to see how to manipulate it for any scenario.

### The General Matrix Representation

We know that the outer product of two state vectors produces a matrix. We also know that with the QFT we have the input state vector and the output state vector so we must be able to compute the QFT matrix using the outer product of these two, namely .

This matrix will compute the entries of the associated -square matrix, where is the number of qubits. Therefore, and as highlighted above, a QFT on a 3-qubit system will require an -square matrix.

### But is it Unitary?

It is easy to show that the QFT is unitary, and, in fact, it is customary to denote it by , so we will do so from now on. We start by multiplying the QFT matrix by its own adjoint:

Writing it this way lets us put and, crucially, which is nothing but by definition of the inner product of basis states. The exponents in the rotation simply add as one expects, and the four summations can be combined in to one as we are summing over the same range. Thus:

Now, the delta function , acting on the rotation $\omega_N^{yx-y’x’}$ will simply convert any in to a . Therefore, we can absorb the delta function in to the rotation, flat-lining any it encounters (including in the summation):

But now the rotation has the representation of another delta function! I.e. , thus

And, again, the delta function is going to turn any in to , and so

Therefore, the QFT matrix is unitary.

## The QFT as a Quantum Circuit

Deriving a quantum circuit for the 3-qubit case is a little difficult to start with. Let’s go back to the 2-qubit case (remember, that means a matrix!). We know that the QFT performs the following mapping on basis states:

Can we do anything with this expression? Well, a quantum circuit is *qubit-dependent* i.e. we will need to know exactly what to do with each qubit if we want to implement a QFT. Therefore, those state vectors in the above representation for a QFT will need to be expanded:

Here we have split out the target state vector as a product of states (standard stuff):

and therefore, the product in the exponent becomes a sum:

But because the original sum goes to , we will essentially have copies of the above sub-summation, so we get:

Now for each element in the exponent summation, we can pair it with exactly one of the ‘s in the target state basis vector, i.e. we could pair the terms like so:

…and there would be of them related by a product. Therefore, we could simply write the the exponential of sum as the product of exponents with appropriately paired terms:

Rearranging the sum and product

Since can either be 0 or 1, we can expand the sum now without the product getting in the way:

To get:

### Expanding the Product Using Fractional Binary Notation

We would like to now expand the

The definition of the **binary fraction** is this:

To see how this is used it is extremely useful to compute some examples. Consider first . Here, ( counts the number of terms in the expansion, since only exists beyond the decimal point ), and also starts from the first index of the first term, which, in this case, is also 1. Thus:

Pretty simple. What about ? Here, there are two terms beyond the decimal point, so . The first index is, again, 1 so starts at 1, and so:

Again, pretty simple.

Things get a little more tricky with . Here, there is again only one term, so , but now must start from as it is the first index in the list. So we get:

What about ? Here, two terms, so . First term index is now so starts from . Notice now that the terms *must be in lexicographical order*. The binary expansion is:

With this little tool in mind, let’s now return to this guy:

Let’s expand the product in our minds and just consider what the *last term* would look like expanded out, recalling that :

…and we can see that the last part of the exponential (the bit) can now be replaced with its binary form:

But there are more terms in the product expansion. Here is the *2nd-last term*:

Taking a common factor of out, we get

Which, the last part in parentheses has binary form: , and so the 2nd last term looks like this:

Continuing in the fashion all the way back to the first term we find a pattern of implementing longer and longer binary representations of the exponent. Eventually we get the full binary representation of the Quantum Fourier Transform:

This is a very useful form of the QFT for, specifically (and don’t forget!) the case where the number of qubits is some power of two, i.e. for .

Why?

### The Most Important Result of this Article

Because take a look at that first qubit:

It’s the ONLY one that depends on ALL values of all the other input qubits . Each further qubit depends less and less on the input qubits! Also, the last single qubit has which equals either or which is the **Hadamard gate/transform**.

## Combining What We Know to Build a Circuit

We already know that the **Hadamard gate** produces the following in a circuit of qubits:

Note how the is consumed inside the exponent.

We also know that the **Rotation Gate** (a.k.a Phase Shift Gate) is

If we now apply controlled rotation gates on the Hadamard transformed state, we get

and we have perfectly reproduced the first term of the above, expanded QFT state.

Then we move to the next qubit, perform another Hadmard, then the appropriate (one fewer) rotation gates, to get the second qubit.

Do this all the way to the end and you have effectively (in binary) produced the logical output of a Fourier transform on qubits!

This is what it looks like on a circuit diagram:

## Summary

In this article we made the giant leap to being able to actually come up with a quantum circuit, at least in theory, starting from a mathematical equation. We had to expand and break up the Fourier transform equation in to bite size pieces, crucially by using its linearity and unitary properties. From here we needed to find a suitable ordering of the embedded product and sums and then re-expand it in binary to get at the individual qubits.

Once we got to that point all we had to do was notice that we were really just looking at a sequence of Hadamard and Rotation transformations! This is particularly easy to do when you have expressed your equation in binary notation.

In the next article we will seek to implement this theoretical circuit of QFT in to a working prototype in Qiskit’s Aqua in Python.

## See Also

**<- Previous** Articles In This Series Next Article ->

Thanks for this great article. I have been working my way through Qiskit tutorials, and always wondering how to get from an engineering problem to a circuit. Your article answers this.

I am working through it slowly. Here is my first question

“Well, we can use qubit notation for a basis state |x\rangle :”

and then:

“Note how x replaces k in the exponent.”

why does x replace k?

Hi dng, yeah, this is a really important question, and one that I struggled a lot with understanding when I first encountered it. I started learning about Quantum Algorithms from the Nielsen & Chuang textbook, and they introduce this “swapping of x to z” in equations (1.49) and (1.50). They say that it “helps to first calculate the effect of the Hadamard transform on a state |x>” by checking all the cases one by one, writing it all out and then looking for simplifications. The whole ordeal can then be “summarised more succinctly as Eq. (1.50)”. Now, I did end up doing this by hand, and I guess it did reveal the tricks involved. However, I am planning on publishing a new blog on this very calculation.

“Furthermore, we can reduce rotations to modulo 8, i.e. if we see a \omega^{10}, for example, we can write this as \omega^{2} because ten is equal to 2 modulo 8.”

Did you mean 2 is equal to 10 modulo 8?

Hi dng, indeed I did!