Quantum Computing II: Quantum Fourier Transform

References


Minimal Background

The quantum fourier transform is useful because it takes a quantum state and allows us to convert phases to binary numbers, and vice versa. This is a useful primitive because phases will often contain information we want to access.

The quantum fourier transform should take the ket $|j\rangle$ (which we should just think of as a binary number) to the state $\frac{1}{\sqrt{N}}\sum_{k=1}^{N-1} \omega^{jk}|k\rangle$ where $\omega=e^{2\pi i/N}$.

One way to think about the unitary matrix $U_\textrm{QFT}$ is the following: Consider the matrix element $\langle k | U_\textrm{QFT} |j \rangle$, a number which tells us how much the state for input binary number $j$ contributes to the state for output binary number $k$. To make our circuit work, we must ensure that every time the input is binary number $j$ and the output is binary number $k$, the input picks up a phase $\omega^{jk}$. Notice that this is just a phase!

You may found the following facts useful:

You can think of the product of $jk$ in the following way:
$j = j_2 2^2+j_1 2^1 + j_0 2^0$
$k = k_2 2^2+ k_1 2^1 + k_0 2^0$
So $jk=(j_2+k_2)2^4+(j_2+k_1)2^3+...$


Building the quantum fourier transform circuit for your simulator

Here is an example of a three-qubit QFT

From wikipedia.
(this graphic is from wikipedia)

Comment 1: There’s something a bit funny about the ordering of the input and output bits (they’re reversed!). That’s going to be a bit inconvenient and we’re going to actually un-reverse the output bits eventually by just swapping things around but let’s worry about that later

Comment 2: This circuit actually uses controlled-phase gates. You will need to convert them into something your simulator can use.

There are a couple additional observations to make:

Start by writing the circuit description for this circuit in your simulator and then check that it gives the same result as the unitary matrix you generated above.

1
2
3
4
    3
    H 2
    ....
    ....
Grading
Show that you've written the correct circuit description for three qubits and that it gets the correct result when you run it through your simulator. Make sure you've reversed the bits at the end. Paste the verification that it gets the right result into your document. One way to do this is to just build the QFT matrix another way and compare with what your description generates.

Now, for any fixed number of qubits, you could probably write out the QFT circuit by hand. But we’d like to do this in a more automated way. We’re going to use the QFT as a subroutine in various places.

Here is the general circuit.
From wikipedia
(From wikipedia)

Grading

Write code that takes a number of wires and produces the circuit description for that number of wires. Test it in your simulator and convince yourself it works correctly.

Paste into your document your QFT on five qubits run in the myInputState file as well as the five qubit QFT description.