Quantum Fourier Transform

The intent of this page is to explain the quantum Fourier transform (QFT). If you're familiar with the classical discrete Fourier transform you'll find the QFT to be very similar.

We first explain how to compute the QFT in a mechanical way. We later discuss the matrix and circuit representations of the QFT. We provide examples of all of these things.

What does the quantum Fourier transform do?

The QFT is a function on \(n\)-qubit states. It maps an \(n\)-qubit \( \psi = \Sigma_{j=0}^{2^{n}-1}x_j|j\rangle \) to another \(n\)-qubit \( QFT( \psi ) = \Sigma_{j=0}^{2^{n}-1}y_j|j\rangle \).

The quantum states \(|j\rangle\) used above denote the binary encoding of the integer \(j\), i.e. \(|0 \rangle = |00...0\rangle\), \(|2\rangle = |00...10\rangle \) and \(|2^n-1\rangle = |11...1\rangle\). There are \(N \equiv 2^n\) such states for an \(n\)-qubit system.

The coefficients \(y_j\) above are computed from the inputs \(x_k\) as follows. $$y_j = \frac{1}{\sqrt{N}}\Sigma_{k=0}^{N-1}x_k e^{2\pi jk i/N} $$ In this equation \(i\) is the complex number so that the \( e^{2\pi jk i/N} \) are periodic with frequency \(jk/N \).

Example with just 1 qubit

With one qubit the input state may be written as \(x_0 |0\rangle + x_1 |1\rangle \). Using the equation above \(y_0 = \frac{1}{\sqrt{2}}(x_0 e^0 + x_1 e^0) = \frac{1}{\sqrt{2}}(x_0 + x_1 )\) and \(y_1=\frac{1}{\sqrt{2}}(x_0 e^0 + x_1 e^{2\pi i/2}) = \frac{1}{\sqrt{2}}(x_0 - x_1 ) \).

If you've studied quantum computing much this result may look familiar. That's because the 1-qubit QFT is behaves just like the Hadamard gate.

Example with 2 qubits

A two qubit state can be written as \( \Sigma_{j=0}^{N-1}x_j |j\rangle \). Using the equation, the output coefficients are as follows. $$y_0 = \frac{1}{2}(x_0+x_1+x_2+x_3)$$ $$y_1 = \frac{1}{2}(x_0+e^{\pi i/2}x_1 + e^{\pi i} x_2 + e^{3\pi i/2} x_3) = \frac{1}{2}(x_0+ix_1- x_2 -ix_3)$$ $$y_2 = \frac{1}{2}(x_0+e^{\pi i}x_1 + e^{2\pi i} x_2 + e^{3\pi i} x_3) = \frac{1}{2}(x_0-x_1 + x_2 - x_3)$$ $$y_3 = \frac{1}{2}(x_0+e^{3\pi i/2}x_1 + e^{3\pi i} x_2 + e^{9\pi i/2} x_3) = \frac{1}{2}(x_0-ix_1 - x_2 + ix_3)$$

Matrix representation

It's often helpful to know the matrix representation of a function like the QFT. To declutter the matrix slightly we'll denote \(e^{2\pi i/N}\) as \(\omega_N\). With this notation you can easily find that the matrix entry in row \(j\) and column \(k\) is simply \(\frac{1}{\sqrt{N}} \omega_N^{jk}\). As examples, the one qubit matrix \(M_1\) and the two qubit matrix \(M_2\) are shown below.

1-qubit QFT matrix

$$ M_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

2-qubit QFT matrix

$$ M_2 = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & \omega_4 & \omega_4^2 & \omega_4^3\\ 1 & \omega_4^2 & \omega_4^4 & \omega_4^6\\ 1 & \omega_4^3 & \omega_4^6 & \omega_4^9 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i \end{bmatrix}$$

Quantum circuit

The QFT may be implemented by a quantum circuit containing only Hadamard gates (\(H\)) and controlled phase gates (\(P(\phi )\)). As an example, the circuit below implements the two qubit QFT. The top input is the most significant qubit, but the bottom output is the most significant qubit.

Let's feed the state \(|2\rangle = |10\rangle\) to this circuit and see what happens. The leading qubit in state \(|1\rangle\) first passes a Hadamard gate to become \(\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\). Since the second input qubit is \(|0\rangle\) the controlled phase gate is inactive, so the next operation is the Hadamard gate on the second qubit which yields \(H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\). Recall the bottom output qubit is the most significant, so we need to flip the order giving result below. $$\frac{1}{2}(|0\rangle + |1\rangle) \otimes (|0\rangle - |1\rangle) = \frac{1}{2}(|00\rangle -|01\rangle + |10\rangle-|11\rangle )$$

To check if the circuit gave the correct answer, and as an exercise, let's compute QFT(\( |10\rangle \)) using the matrix \(M_2\). Since \( |10\rangle \) is the 3rd basis element the column vector \( (0 0 1 0)^T \) is the input.

$$ QFT(|10\rangle ) = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} $$

The resulting column vector matches the result given by the quantum circuit.

Properties of the quantum Fourier transform

The QFT is a unitary transformation. This can be seen from the fact that \(M_n^{\dagger}=M_n^{-1}\).

Inverse quantum Fourier transform

Since the QFT is unitary it is invertible. The formula to compute the inverse is the same aside for a negative in the exponent.

$$y_j = \frac{1}{\sqrt{N}}\Sigma_{k=0}^{N-1}x_k \omega_N^{-jk} $$

As an example, the matrix for the inverse QFT of two qubits \(M_2^{-1}\) is \(M_2^{\dagger}\) shown below.

$$ M_2^{-1} = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i\\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix}$$