< Current Chapter (Quantum Algorithms)< Previous Article (Grover Search)

Quantum Fourier Transform

The quantum Fourier transform (QFT) applies a discrete Fourier transform to the amplitudes of a quantum state. It changes how information is encoded in the state, making it a useful building block for algorithms that work with phases and periodicity.

We'll start with the discrete Fourier transform, rewrite the QFT of a computational basis state as a product of single-qubit states, and use that expression to build a circuit with Hadamard and controlled phase gates.

What you will learn

Interpret the complex phase factors in the discrete Fourier transform.
Use binary fractions to derive the QFT's product representation.
Follow the Hadamard, controlled phase and SWAP gates in a QFT circuit.
Understand why the circuit uses a quadratic number of gates in the number of qubits.

Prerequisites

Start with complex numbers and rotations, bra-ket notation, and the tensor products in Multiple Qubits. You'll also use the Hadamard gate from Single Qubit Gates and controlled operations from Multi Qubit Gates.

The discrete Fourier transform

The discrete fourier transform is a mathematical operation that takes, as input, a sequence of numbers $x_0, \ldots, x_{N-1}$ and outputs a new sequence of numbers $y_0, \ldots, y_{N-1}$ where:

y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_je^{2\pi ijk/N}

Looks scary? Let's break it down.

Firstly, let's revise our complex numbers a bit. Remember that $e^{i \theta}$ merely represents a rotation of $\theta$ radians around the complex unit circle. Since we know that $2\pi$ is a full rotation this means the exponential term is just $jk/N$ full rotations around the circle.

In fact, to make this more obvious we will define a symbol to simplify our equation:

\omega_N = e^{2\pi i/N}

So $\omega_N$ is a $1/N$ -th rotation around the unit circle. $\omega^{2}_N$ is a $2/N$ -th rotation and so on. We can then also see that $\omega^{N}_N$ is the same as $\omega^{0}_N$ since doing a full rotation is the same as doing no rotation. And from there it's fairly clear that we get relations like: $\omega^{2}_N = \omega^{N+2}_N = \omega^{2N+2}_N$ . So we end up with a circular pattern very similar to the powers of $i$ .

Just to be clear, let's now re-write our original equation with $\omega$ :

y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_{N}^{jk}

So our fourier transform is starting to make some more sense. Each term $y_k$ in the output sequence is a sum of all the input terms $x_j$ multiplied by a rotation of $jk/N$ around the unit circle.

The rotation patterns can be seen easier if we look at a concrete example in the case when $N=5$ :

y_0 = \frac{1}{\sqrt{N}}(x_0\omega^0_5 +x_1\omega^0_5 +x_2\omega^0_5 +x_3\omega^0_5 +x_4\omega^0_5) \\[3ex] y_1 = \frac{1}{\sqrt{N}}(x_0\omega^0_5 +x_1\omega^1_5 +x_2\omega^2_5 +x_3\omega^3_5 +x_4\omega^4_5) \\[3ex] y_2 = \frac{1}{\sqrt{N}}(x_0\omega^0_5 +x_1\omega^2_5 +x_2\omega^4_5 +x_3\omega^6_5 +x_4\omega^8_5) \\[3ex] y_3 = \frac{1}{\sqrt{N}}(x_0\omega^0_5 +x_1\omega^3_5 +x_2\omega^6_5 +x_3\omega^9_5 +x_4\omega^{12}_5) \\[3ex] y_4 = \frac{1}{\sqrt{N}}(x_0\omega^0_5 +x_1\omega^4_5 +x_2\omega^8_5 +x_3\omega^{12}_5 +x_4\omega^{16}_5)

We can then simplify all of our omegas using the rules we learned earlier:

y_0 = \frac{1}{\sqrt{N}}(x_0 +x_1 +x_2 +x_3 +x_4) \\[3ex] y_1 = \frac{1}{\sqrt{N}}(x_0 +x_1\omega^1_5 +x_2\omega^2_5 +x_3\omega^3_5 +x_4\omega^4_5) \\[3ex] y_2 = \frac{1}{\sqrt{N}}(x_0 +x_1\omega^2_5 +x_2\omega^4_5 +x_3\omega^1_5 +x_4\omega^3_5) \\[3ex] y_3 = \frac{1}{\sqrt{N}}(x_0 +x_1\omega^3_5 +x_2\omega^1_5 +x_3\omega^4_5 +x_4\omega^2_5) \\[3ex] y_4 = \frac{1}{\sqrt{N}}(x_0 +x_1\omega^4_5 +x_2\omega^3_5 +x_3\omega^2_5 +x_4\omega^1_5)

It's not immediately clear what's useful about this. Usually this idea is first presented in a mathematics course where it can be used to analyze signals. In that context, the fourier transform is used to decompose a signal into its constituent frequencies. This is useful because it allows us to understand the signal better and to filter out noise.

For our case though, we'll simply stick with the definition and see how we can apply this to our quantum algorithms. It's use will hopefully become apparent later.

From the discrete transform to the QFT

The quantum Fourier transform is a linear operation. On a computational basis state $\ket{y}$ , it acts as follows:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\omega_N^{yj}\ket{j}

Here $y$ labels the input basis state, and $j$ runs over the output basis states. The phase factors depend on both indices. For a superposition input, apply this rule to each basis state and add the results with the original amplitudes.

Note also that although $y$ and $j$ are used like normal numbers in this equation, we know that the kets are actually formed of a tensor product of $\ket{1}$ s and $\ket{0}$ s that are the binary representation of the number. We should therefore assume that $y$ and $j$ are formed from the same number of bits and therefore $N = 2^n$ for some $n$ .

Deriving the product representation

To understand how we implement this in a quantum circuit, we will use some algebra to transform this summation formula into a different tensor product form, that will more easily translate into a circuit.

To do this, our first step is to split the $j$ summation into it's individual bits:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\sum_{j_1=0}^{1} \ldots \sum_{j_n=0}^{1}\omega_N^{yj}\ket{j_1, \ldots, j_n}

Then we'll look at a slightly different representation of our $\omega$ term. We know that $\omega_N^{yj} = e^{2\pi iyj/N}$ . But since $N = 2^n$ the division by $N$ here is simply shifting the bits of $j$ to after the decimal point. i.e. if $n = 4$ and $j = 0101$ in binary, then we have $j/2^n = j/N = 0.0101$ .

In general, this shifting the bits to the right of the decimal point can be represented as:

j/N = j/2^n = \sum_{l=1}^{n}j_l2^{-l}

So our $\omega$ term becomes:

\omega_N^{yj} = e^{2\pi iy\sum_{l=1}^{n}j_l2^{-l}}

And our main equation becomes:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\sum_{j_1=0}^{1} \ldots \sum_{j_n=0}^{1}e^{2\pi iy\sum_{l=1}^{n}j_l2^{-l}}\ket{j_1, \ldots, j_n}

Since the exponential co-efficient is now represented as a sum of $j$ s individual bits, we can also separate the ket into a tensor product of the individual bits:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\sum_{j_1=0}^{1} \ldots \sum_{j_n=0}^{1}e^{2\pi iyj_12^{-1}}\ket{j_1} \otimes \ldots \otimes e^{2\pi iyj_n2^{-n}}\ket{j_n} \\[3ex] = \frac{1}{\sqrt{N}}\sum_{j_1=0}^{1} \ldots \sum_{j_n=0}^{1} \bigotimes_{l=1}^{n}e^{2\pi iyj_l2^{-l}}\ket{j_l}

And now, since we know the tensor product stitches together the $\ket{1}$ s and $\ket{0}$ s, we can move the tensor product to the outside to do this instead of summing over each bit:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\sum_{j_l=0}^{1}e^{2\pi iyj_l2^{-l}}\ket{j_l}

And now our summation is just for 2 terms, so we can remove the big summation and write it explicitly:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\Bigl[e^{2\pi iy0\cdot 2^{-l}}\ket{0} + e^{2\pi iy1 \cdot 2^{-l}}\ket{1}\Bigr] \\[3ex] \operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\Bigl[\ket{0} + e^{2\pi iy2^{-l}}\ket{1}\Bigr]

The last step will involve that $y2^{-l}$ term in the exponent. If $y$ has bits $y_1,\ldots,y_n$ then multiplying by $2^{-l}$ is shifting these bits $l$ places to the right. e.g. if $y = 01011$ and $l=3$ we have $y2^{-l} = 01.011$ . In general this is of the form: $y2^{-l} = y_1 \ldots y_{n-l}.y_{n-l+1} \ldots y_n$ where the decimal place ends up between the $n-l$ th and $n-l+1$ th digit.

But, notice that this number is multiplying $2\pi i$ in the exponent so any whole part of this number (i.e. any number to the left of the decimal point) represents a full rotation so can be ignored. So we end up with:

\operatorname{QFT}\ket{y} = \frac{1}{\sqrt{N}}\bigotimes_{l=1}^{n}\Bigl[\ket{0} + e^{2\pi i0.y_{n-l+1}\ldots y_n}\ket{1}\Bigr]

To clean this up, let's drop the big $\otimes$ symbol and replace $N$ with $2^n$ :

\operatorname{QFT}\ket{y} = \frac{(\ket{0} + e^{2\pi i0.y_n}\ket{1})(\ket{0} + e^{2\pi i0.y_{n-1}y_n}\ket{1}) \ldots (\ket{0} + e^{2\pi i0.y_1 \ldots y_n}\ket{1})}{2^{n/2}}

This is the product representation of the quantum fourier transform. It's useful because it better shows the behaviour on individual bits and will allow us to construct a circuit easier.

Building the QFT circuit

To build the circuit, we'll need to invent some new gates. The quantum gates we've studied previously have mostly been focussed with discrete jumps around the Bloch Sphere. As we can see from our equation above, the quantum fourier transform will involve rotations of the phase of the $\ket{1}$ state. So let's create the gates:

R_x\ket{0} = \ket{0} \\[3ex] R_x\ket{1} = e^{2\pi i / 2^x}\ket{1}

So all of these gates leave the $\ket{0}$ state alone and rotate the phase of the $\ket{1}$ state by a $1/2^x$ th of a full rotation. i.e. $R_1$ rotates $\ket{1}$ by 180 degress and $R_2$ rotates $\ket{1}$ by 90 degrees etc.

Let's now present the quantum circuit for the quantum fourier transform and then examine why it works:

The quantum circuit for the quantum fourier transform consisting of Hadmard gates and R gates

Notice that our $R$ gates are controlled gates. Just like we've seen other controlled gates previously, these gates only apply their rotation if the control qubit is in the $\ket{1}$ state.

To see that this works, let's start by just following the $\ket{y_1}$ qubit for now.

Applying the first Hadamard gate gives us $\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.y_1}\ket{1})$ since if $y_1 = 0$ then $e^{2\pi i0.y_1} = 1$ and if $y_1 = 1$ then $e^{2\pi i0.y_1} = -1$ .

The controlled $R_2$ gate then takes us to $\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.y_1y_2}\ket{1})$ since the $\ket{1}$ state will undergo a further 90 degree rotation if $y_2 = 1$ .

Continuing on in this fashion, the first qubit ends in the state $\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i0.y_1 \ldots y_n}\ket{1})$ . Our total state so far is then:

\frac{(\ket{0} + e^{2\pi i0.y_1 \ldots y_n}\ket{1})}{2^{1/2}}\ket{y_2, \ldots, y_n}

Continuing in this fasion we apply one fewer rotation for each qubit, so following the same steps for the second qubit brings us to:

\frac{(\ket{0} + e^{2\pi i0.y_1 \ldots y_n}\ket{1})(\ket{0} + e^{2\pi i0.y_2 \ldots y_n}\ket{1})}{2^{2/2}}\ket{y_3, \ldots, y_n}

Following the pattern for the rest of our qubits gives the circuit state before reversing the output qubits, which we'll call $\ket{\psi_{\mathrm{rev}}}$ :

\ket{\psi_{\mathrm{rev}}} = \frac{(\ket{0} + e^{2\pi i0.y_1 \ldots y_n}\ket{1})(\ket{0} + e^{2\pi i0.y_2 \ldots y_n}\ket{1}) \ldots (\ket{0} + e^{2\pi i0.y_n}\ket{1})}{2^{n/2}}

Reversing the output qubits

This is almost what we want, but notice that the qubits are actually backwards compared to our equation from earlier!

This is easily solved by using $\lfloor n/2 \rfloor$ $\text{SWAP}$ gates to move the positions of the qubits.

After these SWAP gates, the output is $\operatorname{QFT}\ket{y}$ . So we've found a circuit that implements the quantum Fourier transform!

How many gates does the QFT need?

We apply $n$ gates to the first qubit, $n-1$ gates to the 2nd etc. followed by $\lfloor n/2 \rfloor$ $\text{SWAP}$ gates so we end up using a total of $(n + (n - 1) + \ldots + 2 + 1) + \lfloor n/2 \rfloor = \frac{n(n+1)}{2} + \lfloor n/2 \rfloor$ gates. So this is fairly efficient, no exponential scaling.

This gives us an $O(n^2)$ -gate circuit on $n$ qubits, treating each controlled phase gate as one gate. Its output is a quantum state: measuring it does not reveal every transformed amplitude. This distinction matters when comparing the QFT with a classical Fourier transform that returns a list of numbers.

Related lessons

Order Finding: see how the QFT helps extract periodic structure.
Shor's Algorithm: connect order finding to integer factorisation.
Grover Search: compare a search algorithm based on amplitude amplification.
Quantum algorithms: the chapter that continues from this transform through order finding to Shor's algorithm.

> Next Article (Order Finding)

Additional Materials

About