Make the Quantum Fourier Transform easy to understand with simple examples

This article helps build an intuitive understanding of the Quantum Fourier Transform through concrete examples.

Amazon Braket Learning Course

You can efficiently learn the basic knowledge of quantum computing-including quantum gates and quantum circuits as well as how to use Amazon Braket through this course.

https://www.udemy.com/course/quantum-computing-on-aws-for-beginners-amazon-braket/?referralCode=F361C3FD774489A1B5B8

This course is designed for those with no prior knowledge of quantum computing or AWS, and by the end, you’ll even be able to learn about quantum machine learning. Take advantage of this opportunity to build your skills in quantum technologies!

Regarding the IBM Quantum Developer Certification Exam

IBM offers a certification exam related to Qiskit, which is introduced in this blog.

By obtaining this certification, you can prove your knowledge of Qiskit and quantum programming. For those aiming to achieve this certification, I have created a practice exams on the Udemy platform! I have made the explanations as clear as possible, so please make sure to take full advantage of the following practice exams as extra study material for exam preparation.

Practice exams

https://www.udemy.com/course/ibm-certified-quantum-computation-qiskit-practice-exams/?referralCode=3B3263DF800E05439AD2

Quantum Fourier Transform

The Quantum Fourier Transform $\mathcal{F}$ on $n$ qubits can be expressed by the following equation. $$ \mathcal{F} \ket{j} = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i jk / 2^n} \ket{k} $$

It is also worth mentioning that the Quantum Fourier Transform is unitary, and its inverse can be written as follows. $$ \mathcal{F}^{-1} \ket{k} = \mathcal{F}^\dagger \ket{k} = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} e^{-2\pi i jk / 2^n} \ket{j} $$

Concrete examples of the Quantum Fourier Transform

For a single qubit

Let’s apply the quantum Fourier transform to the state $\ket{0}$.

$$ \mathcal{F} \ket{0} = \frac{1}{\sqrt{2}} ( \ket{0} + \ket{1} ) $$ As you can see, $\ket{0}$ becomes a superposition of states with no phase shift.

Let’s apply the quantum Fourier transform to the state $\ket{1}$.

$$ \mathcal{F} \ket{1} = \frac{1}{\sqrt{2}} ( \ket{0} + e^{\pi i} \ket{1} ) = \frac{1}{\sqrt{2}} ( \ket{0} - \ket{1} ) $$ As you can see, the Quantum Fourier Transform of $\ket{1}$ becomes a superposition where each component has a phase shift of π, indicating a phase-inverted state.

For two qubits

Let’s apply the quantum Fourier transform to the state $\ket{00}$.

$$ \mathcal{F} \ket{00} = \frac{1}{2} ( \ket{00} + \ket{01} + \ket{10} + \ket{11} ) $$ Similarly, we can see that $\ket{00}$ also becomes a superposition of states with no phase shift, just like $\ket{0}$.

Let's apply the quantum Fourier transform to the state $\ket{01}$.

$$ \begin{align} \mathcal{F} \ket{01} &= \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i \cdot 1 \cdot k / 4} \ket{k} = \frac{1}{2} \left( \ket{00} + e^{\frac{\pi i}{2}}\ket{01} + e^{\frac{2\pi i}{2}} \ket{10} + e^{\frac{3\pi i}{2}} \ket{11} \right) \\ &= \frac{1}{2} \left( \ket{00} + i\ket{01} - \ket{10} - i\ket{11} \right) \\ \end{align} $$ As you can see, applying the Quantum Fourier Transform to $\ket{01}$ results in a superposition of states with phase shifts incremented by $\frac{\pi}{2}$.

Let's apply the quantum Fourier transform to the state $\ket{10}$.

$$ \begin{align} \mathcal{F} \ket{10} &= \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i \cdot 2 \cdot k / 4} \ket{k} = \frac{1}{2} \left( \ket{00} + e^{\pi i} \ket{01} + e^{2\pi i} \ket{10} + e^{3\pi i} \ket{11} \right) \\ &= \frac{1}{2} \left( \ket{00} - \ket{01} + \ket{10} - \ket{11} \right) \end{align} $$ As you can see, applying the Quantum Fourier Transform to $\ket{10}$ results in a superposition of states with phase shifts incremented by $\pi$.

Let's apply the quantum Fourier transform to the state $\ket{11}$.

$$ \begin{align} \mathcal{F} \ket{11} &= \frac{1}{2} \sum_{k=0}^{3} e^{2\pi i \cdot 3 \cdot k / 4} \ket{k} = \frac{1}{2} \left( \ket{00} + e^{\frac{3\pi i}{2}} \ket{01} + e^{\frac{6\pi i}{2}} \ket{10} + e^{\frac{9\pi i}{2}} \ket{11} \right) \\ &= \frac{1}{2} \left( \ket{00} - i\ket{01} - \ket{10} + i\ket{11} \right) \end{align} $$ As you can see, applying the Quantum Fourier Transform to $\ket{11}$ results in a superposition of states with phase shifts incremented by $\frac{3\pi}{2}$.

For three qubits

Let’s apply the quantum Fourier transform to the state $\ket{000}$.

$$ \mathcal{F} \ket{000} = \frac{1}{\sqrt{8}} \left( \ket{000} + \ket{001} + \ket{010} + \ket{011} + \ket{100} + \ket{101} + \ket{110} + \ket{111} \right) $$ It is also evident that the Quantum Fourier Transform of $\ket{000}$ becomes a superposition where all components have zero phase shift.

Let's apply the quantum Fourier transform to the state $\ket{001}$. 　 $$ \begin{align} \mathcal{F} \ket{001} &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2\pi i \cdot 1 \cdot k / 8} \ket{k} \\ &= \frac{1}{\sqrt{8}} \left( \ket{000} + e^{\frac{\pi i}{4}} \ket{001} + e^{\frac{2\pi i}{4}} \ket{010} + e^{\frac{3\pi i}{4}} \ket{011} + e^{\frac{4\pi i}{4}} \ket{100} + e^{\frac{5\pi i}{4}} \ket{101} + e^{\frac{6\pi i}{4}} \ket{110} + e^{\frac{7\pi i}{4}} \ket{111} \right) \\ &= \frac{1}{\sqrt{8}} \left( \ket{000} + e^{\frac{\pi i}{4}} \ket{001} + i \ket{010} + e^{\frac{3\pi i}{4}} \ket{011} - \ket{100} + e^{\frac{5\pi i}{4}} \ket{101} - i \ket{110} + e^{\frac{7\pi i}{4}} \ket{111} \right) \end{align} $$

As you can see, applying the Quantum Fourier Transform to $\ket{001}$ results in a superposition of states with phase shifts incremented by $\frac{\pi}{4}$.

Let's apply the quantum Fourier transform to the state $\ket{010}$. 　 $$ \begin{align} \mathcal{F} \ket{010} &= \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2\pi i \cdot 2k / 8} \ket{k} \\ &= \frac{1}{\sqrt{8}} \left( \ket{000} + e^{\frac{\pi i}{2}} \ket{001} + e^{\frac{2\pi i}{2}} \ket{010} + e^{\frac{3\pi i}{2}} \ket{011} + e^{\frac{4\pi i}{2}} \ket{100} + e^{\frac{5\pi i}{2}} \ket{101} + e^{\frac{6\pi i}{2}} \ket{110} + e^{\frac{7\pi i}{2}} \ket{111} \right) \\ &= \frac{1}{\sqrt{8}} \left( \ket{000} + i\ket{001} - \ket{010} - i\ket{011} + \ket{100} + i\ket{101} - \ket{110} - i\ket{111} \right) \end{align} $$

As you can see, applying the Quantum Fourier Transform to $\ket{010}$ results in a superposition of states with phase shifts incremented by $\frac{\pi}{2}$.

From these examples, we can see the rule that each state is summed while shifting the phase depending on the number of qubits and the value of the original state.

Benefits of the Quantum Fourier Transform

For instance, consider a two-qubit system that is in either state $\psi_1 = \frac{1}{2} \left( \ket{00} + i\ket{01} - \ket{10} - i\ket{11} \right)$ or state $\psi_2 = \frac{1}{2} \left( \ket{00} - \ket{01} + \ket{10} - \ket{11} \right)$.
How can we determine whether the system is in state $\psi_1$ or state $\psi_2$?
First, as a fundamental principle of quantum mechanics, it is not possible to directly observe the coefficients of all states.

Furthermore, measuring the two-qubit state as is does not help, since both $\psi_1$ and $\psi_2$ yield identical probability distributions due to having the same absolute amplitudes.

00: 25%, 01: 25%, 10: 25%, 11: 25%

In such cases, the quantum Fourier transform and its inverse can be useful.
For example, applying the Quantum Fourier Transform to $\psi_1$ results in a state $\ket{01}$. Applying the Quantum Fourier Transform to $\psi_2$ results in a state $\ket{10}$.

In either case, we first perform the inverse Quantum Fourier Transform, and if $\ket{01}$ is observed, we know that the original state was $\psi_1$, while if $\ket{10}$ is observed, we know that it was $\psi_2$.
This illustrates one of the key strengths of the Quantum Fourier Transform: the ability to extract information about the quantum state, including its phase.
In the next article, we will use Qiskit 2.0 to implement the inverse Quantum Fourier Transform and demonstrate that the original quantum state can be successfully identified.