Understanding the fourier transform

Approach I

Now, we are going to understand the fourier transform.

Recall that the QFT does

$\frac{1}{\sqrt{N}}\sum_{k=1}^{N-1} \omega^{jk}|k\rangle$ where $\omega=e^{2\pi i/N}$.

We can write $j$ and $k$ in binary. So $j=j_2 j_1 j_0 = j_2 2^2 + j_1 2^1 + j_0 2^0$

Then $jk = (j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2 + (j_2 k_1 + j_1 k_2 ) 2^3 + (j_2 k_2) 2^4 + (j_1 k_0 + j_0 k_1) 2^1 + (j_0 k_0) 2^0$

Write a circuit (and send it through your simulator) that does the following (first convince yourself that's unitary):
$\frac{1}{\sqrt{N}}\sum_{k=1}^{N-1} \omega^{(j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2}|k\rangle$ where $\omega=e^{2\pi i/N}$.

Now build a circuit which does
$\frac{1}{\sqrt{N}}\sum_{k=1}^{N-1} \omega^A |k\rangle$ where $\omega=e^{2\pi i/N}$
where $A=(j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2 + (j_2 k_1 + j_1 k_2 ) 2^3 + (j_2 k_2) 2^4$

Then
$A=(j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2 + (j_2 k_1 + j_1 k_2 ) 2^3 + (j_2 k_2) 2^4 + (j_1 k_0) 2^1$

Next
$A=(j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2 + (j_2 k_1 + j_1 k_2 ) 2^3 + (j_2 k_2) 2^4 + (j_1 k_0) 2^1 + (j_0 k_1) 2^1$

and finally
$A=(j_2 k_0 + j_1 k_1 + j_0 k_2) 2^2 + (j_2 k_1 + j_1 k_2 ) 2^3 + (j_2 k_2) 2^4 + (j_1 k_0) 2^1 + (j_0 k_1) 2^1 + (j_0 k_0) 2^0$


Approach II

The QFT can also be written this way: $$|j_0,j_1,j_2 \rangle \rightarrow \frac{1}{\sqrt{2^3}} \left(|0\rangle + e^{2\pi i[0.j_2]}|1\rangle\right) \otimes \left(|0\rangle + e^{2\pi i[0.j_1j_2]}|1\rangle \right) \otimes \left(|0\rangle + e^{2\pi i[0.j_0 j_1 j_2]}|1\rangle \right) $$

Note: In this formula, these are written out in binary. So, each $j_m$ is really just 0 or 1.

Naively it almost looks like each wire is doing its own separate thing (since it’s just a tensor product at the end of the day). This would mean it’s completely un-entangled and should be able to be applied using single-qubit gates. Why is this not completely correct?

It’s not completely correct because the output of wire 2 depends on the input of wire 2 and 3. Therefore there must be some gates that go between things.

First understand why this gives you back the QFT from above.

Then make a circuit that consists of just one wire and does the right thing on the first wire. Verify it works.

Now, make a circuit that consists of two wires and does the right thing on the first two wire (i.e. make the second wire work) Verify that it works.

Finally, make a circuit that consists of three wires and does the correct thing on all three wires.


Approach III

We also saw above that the QFT can be understood recursively.

First let's convince ourselves that this should be true. Suppose we have a quantum fourier transform on the bottom $n-1$ wires as well as nothing on the top wire. What is the state? Make your circuit do this and verif you get the correct thing (notice that $N$ is different).

Now, when you add the top wire, you've essentially changed the total value of $N$ (by how much?). This means that you have to change the phase on all the bottom wires. How are you going to do this and make it work.

After you understand how this works, go ahead and write some code that takes a QFT on $n-1$ wires and generates a QFT on $n$ wires. Check that it works.