10 Discrete Fourier Transformation

In Chapter 11, we will discuss Shor’s algorithm, which requires the Discrete Fourier Transformation (DFT). Generally, a Fourier transformation is a mathematical technique that decomposes a function into its constituent frequencies. We use the DFT to find the period of a vector.

10.1 Definition of the DFT

The DFT is defined as follows:

Definition 10.1 (Discrete Fourier Transformation) The discrete Fourier transform (DFT) is a linear transformation on \(\mathbb{C}^N\) represented by the matrix \[ \operatorname{DFT}_N \coloneqq \frac{1}{\sqrt{N}} (\omega^{kl})_{kl=0,\dots,N-1} \in \mathbb{C}^{N\times N} \] with \(\omega = e^{2i\pi/N}\), which is the \(N\)-th root of unity.

It applies \(\omega^N=1\) and \(\omega^i \neq 1\) for all \(0 < i < N\).

This transformation is best imagined as a process that takes a periodic vector as an input and outputs the period of that vector. The DFT has some important properties which will help us later on.

Theorem 10.1 (Properties of the DFT) Here are some properties of the DFT which can be used without further proof.

The \(\operatorname{DFT}_N\) is unitary.
\(\omega^t = \omega^{t\mod N}\) for all \(t \in \mathbb{Z}\).
Let \(t \mid N\) and \(s\) be integers and the quantum state \(\psi \in \mathbb{C}^N\) be given by \[ \psi_i \coloneqq \begin{cases} \sqrt{\frac{t}{N}} & \text{if } i = at+s \text{ for some } a \\ 0 & \text{else.} \end{cases} \] In other words \(\psi\) is \(t\)-periodic. Then for \(\phi \coloneqq \operatorname{DFT}_N\) we have \[ |\phi_i| = \begin{cases} \frac{1}{\sqrt{t}} & \text{if } \frac{N}{t} \mid i \\ 0 & \text{else.} \end{cases} \] The first peak of \(\phi\) (besides \(\phi_0\)) is at \(\frac{N}{t}\).

10.2 Constructing the DFT

So far we have described everything necessary for Shor’s algorithm, but only described the matrix representation of the \(\operatorname{DFT}_N\). We will now take a closer look into implementing the \(\operatorname{DFT}_M\) as a quantum circuit. Since we only use the \(\operatorname{DFT}_N\) for Shor’s algorithm so far, we will only look at \(N=2^n\), which is the \(\operatorname{DFT}\) applied on \(n\) qubits.

To start the circuit, we recall the definition of the \(\operatorname{DFT}_N\) from Definition 10.1: \(\operatorname{DFT}_N \coloneqq \frac{1}{\sqrt{{2^n}}} (\omega^{kl})_{kl}\) with \(\omega \coloneqq e^{2\pi i / 2^n}\). To apply the \(\operatorname{DFT}_N\) to a quantum state \(\ket{j}\) we calculate \[ \begin{aligned} \operatorname{DFT}_{N}\ket{j} =& \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega^{jk} \ket{k}\\ =& \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i j k / N} \ket{k}\\ =& \frac{1}{\sqrt{N}} \sum_{k_1 \in \{0,1\}} \dots \sum_{k_n \in \{0,1\}} e^{2\pi i j (\sum_{l=1}^n k_l 2^{-l})} \ket{k_1 \dots k_n}\\ =& \frac{1}{\sqrt{N}} \sum_{k_1 \in \{0,1\}} \dots \sum_{k_n \in \{0,1\}} \bigotimes_{l=1}^n e^{2\pi i j k_l 2^{-l}} \ket{k_l}\\ =& \frac{1}{\sqrt{N}} \bigotimes_{l=1}^n \sum_{k_l \in \{0,1\}} e^{2\pi i j k_l 2^{-l}} \ket{k_l}\\ =& \frac{1}{\sqrt{N}} \bigotimes_{l=1}^n (\ket{0} + e^{2\pi i j 2^{-l}} \ket{1})\\ =& \frac{1}{\sqrt{N}} \bigotimes_{l=1}^n (\ket{0} + e^{2\pi i 0.j_{n-l+1} \dots j_{n}} \ket{1}). \end{aligned} \] The expression \(0.j\) expresses a binary fraction (e.g. \(0.101 = \frac{1}{2} + \frac{1}{8} = \frac{5}{8}\)).

With this we have shown, that we can write \(\operatorname{DFT}_N \ket{j}\) as the following tensor product of quantum states

\[ \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_n} \ket{1}) \otimes \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_{n-1}j_n} \ket{1}) \otimes \dots \otimes \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_1\dots j_n} \ket{1}). \]

From this rewritten tensor product, we can get an idea on how to construct the quantum circuit for the \(\operatorname{DFT}_N\). Namely, we can construct a quantum circuit for each element of the tensor product and from this build the general circuit.

For this, we segment the tensor product into different elements \(\psi\) as follows:

\[ \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_n} \ket{1})}_{\psi_1} \otimes \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_{n-1}j_n} \ket{1})}_{\psi_2} \otimes \dots \otimes \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_1\dots j_n} \ket{1})}_{\psi_n}. \]

We also introduce a new gate \(R_k\) which is defined by the following matrix:

\[ R_k:=\begin{pmatrix} 1 & 0 \\ 0 & e^{2 \pi i / 2^k} \end{pmatrix}. \]

To understand the construction of the circuit from these elements, we will look at an example for \(n=3\) first:

Example: Construction of the DFT circuit for \(n=3\)

We start by building the tensor product for \(n=3\). The input for the DFT circuit is \(\ket{j} = \ket{j_1j_2j_3}\). Using the formula from above, we can write the result of \(\operatorname{DFT}_{2^3} \ket{j}\) as the following tensor product:

\[ \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_3} \ket{1})}_{\psi_1} \otimes \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_2j_3} \ket{1})}_{\psi_2} \otimes \underbrace{\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_1j_2j_3} \ket{1})}_{\psi_3}. \]

The DTF for three qubits

First we construct the \(\psi_3\) element. Contrary to the intuition, we use the top wire containing \(\ket{j_1}\) for this. We use a Hadamad-gate to bring \(\ket{j_1}\) into the superposition \(\frac{1}{\sqrt{2}}(\ket{0} + (-1)^{j_1} \ket{1}) = \frac{1}{\sqrt{2}}(\ket{0} + e^{2 \pi i 0.j_1} \ket{1})\). This looks close to \(\psi_3\) already, we now need to add the last two decimal places \(j_2j_3\) to the state. For this we use \(R_2\) and \(R_3\). We apply \(R_2\) controlled by the wire \(j_2\) and \(R_3\) controlled by the wire \(j_3\). This means, that we only apply the \(R\)-gate, if the corresponding wire contains a \(1\). You can see this written as a quantum circuit at the figure below. After applying \(R_2\) we have the state \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2 \pi i 0.j_1j_2} \ket{1})\) and after applying \(R_3\) we have the state \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2 \pi i 0.j_1j_2j_3} \ket{1})\) on the top wire. This is the same as \(\psi_3\), so we are done on the first wire (We are at the first slice in the figure).
The next step is to construct the \(\psi_2\) state on the middle wire. We again use a Hadamad-gate to bring \(\ket{j_2}\) into the superposition \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2 \pi i 0.j_2} \ket{1})\). We now need to include the last decimal point \(j_3\), for which we use \(R_2\) again, this time controlled by \(j_3\). The resulting superposition is now \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i 0.j_2j_3} \ket{1})\), which is \(\psi_2\). (We are at the second slice in the figure).
On the bottom wire, we can just do a Hadamad-gate to bring \(\ket{j_3}\) into the superposition \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2 \pi i 0.j_3} \ket{1})\). We then have \(\psi_1\) on the bottom wire. (We are at the third slice in the figure).
When applying this circuit, we get the state \(\psi_3 \otimes \psi_2 \otimes \psi_1\) as a result. This very close to our desired state \(\psi_1 \otimes \psi_2 \otimes \psi_3\), just the order of the wires is flipped. To solve this, we apply a \(\operatorname{SWAP}\) onto all wires, which flips the order of the wires an delivers the correct output for \(\operatorname{DFT}_{2^3}\).

The more general approach to construct the \(\operatorname{DFT}_N\) as a quantum circuit with \(n\) qubits (\(N = 2^n\)) works as follows:

Initialize wires with input \(\ket{j}\), so that \(\ket{j_1}\) is on the top wire and \(\ket{j_n}\) is on the bottom wire. Note, that this is not part of the circuit yet.
Start with the top wire. For each wire \(j_i\) do the following:
1. Apply a Hadamad-gate on the wire \(j_i\).
2. For each wire \(j_k\) below the current wire \(j_i\) (with \(i < k \leq n\)), add a \(R_{k-i+1}\)-gate controlled by \(j_k\). Start with \(k = i+1\) (if \(i<n\), else stop).
Perform a \(\operatorname{SWAP}\) to flip all the wires. This means, that the first wire is swapped with the last wire, the second wire is swapped with the second to last wire and so on.

Note: If the the output of the DFT circuit is measured right after applying it (as in Shor’s algorithm) or if the rest of the algorithm allows for it, it is more efficient to perform the \(\operatorname{SWAP}\) classically, since this is considered to be the cheaper operation.

The more general layout of the quantum circuit for the \(\operatorname{DFT_N}\) with the \(\operatorname{SWAP}\) is shown in this figure.