## Quantum Fourier transform

I’m going to study quantum algorithms in my own way using qiskit. This is a record of my personal study, so I may have left out a lot of explanations.

I am following the qiskit website.

Next, let’s review the quantum Fourier transform. I thought I understood it when I was in school, but I’ve completely forgotten it, so I’m going to have to relearn it from scratch.

### github

• The file in jupyter notebook format is here .

• If you want to run it on google colaboratory here

### Author’s environment

!sw_vers

ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G103

Python -V

Python 3.8.5


Import the basic libraries and check their versions.

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import matplotlib
import matplotlib.pyplot as plt
import scipy
import numpy as np
import pandas as pd

print('matplotlib version :', matplotlib.__version__)
print('scipy version :', scipy.__version__)
print('numpy version :', np.__version__)
print('pandas version :', pd.__version__)

matplotlib version : 3.3.2
scipy version : 1.5.2
numpy version : 1.19.2
pandas version : 1.1.3

import qiskit
import json

dict(qiskit.__qiskit_version__)

{'qiskit-terra': '0.17.4',
'qiskit-aer': '0.8.2',
'qiskit-ignis': '0.6.0',
'qiskit-ibmq-provider': '0.13.1',
'qiskit-aqua': '0.9.1',
'qiskit': '0.26.2',
'qiskit-nature': None,
'qiskit-finance': None,
'qiskit-optimization': None,
'qiskit-machine-learning': None}


## Review of the Discrete Fourier Transform

The Fourier transform comes from the Fourier idea that the function $f(x)$ can be represented as a sum of trigonometric functions with various wavenumbers.

$$f(x)=\frac{a_{0}}{2}+a_{1} \cos \frac{\pi x}{L}+b_{1} \sin \frac{\pi x}{L}+a_{2} \cos \frac{2 \pi x}{L}+b_{2} \sin \frac{2 \pi x}{L}+\cdots$$

Here, $a_1$, $b_1$, etc. are the amplitudes of the trigonometric functions with their respective wavenumbers, which can be thought of as the weights of the trigonometric decomposition of the function $f(x)$. To find these amplitudes, we can use the trigonometric formula as follows.

$$a_{n}=\frac{1}{L}\int_{-L}^{L} f(x) \cos \frac{n \pi x}{L} d x \quad(n=0,1,2, \cdots)$$

$$b_{n}=\frac{1}{L} \int_{-L}^{L} f(x) \sin \frac{n \pi x}{L} d x \quad(n=1,2, \cdots)$$

It seems that each amplitude is called a Fourier coefficient.

If we give this as $L \rightarrow \infty$ and transform $\cos$ and $\sin$ using Euler numbers, we get the following formula.

\begin{aligned} &{F}(k)=\frac{1}{\sqrt{2 \pi}}\int_{-\infty}^{\infty} f(x) e^{-i k x} d x \\ &f(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\hat{F}(k) e^{i k x} d k \end{aligned}

Now we have the assumption that the function $f(x)$ is a continuous function, but if we discretize it, we get

\begin{aligned} y_{k}=\frac{1}{\sqrt{2^{n}}} \sum_{j=0}^{2^{n}-1} x_{j} \exp \left(i \frac{2 \pi k j}{2^{n}}\right) \\ x_{k}=\frac{1}{\sqrt{2^{n}}} \sum_{j=0}^{2^{n}-1} y_{j} \exp \left(-i \frac{2 \pi k j}{2^{n}}\right) \end{aligned}

This can be converted to This corresponds to a mapping from the vector $\left(x_{0}, \ldots, x_{N-1}\right)$ to the vector $\left(y_{0}, \ldots, y_{N-1}\right)$.

Fourier transform is an indispensable technology in the real world. I have been designing analog circuits and semiconductors during my businessman days, and I cannot develop devices without it.

## Quantum Fourier Transform

Let’s apply the previous discussion to the transformation of quantum states. Let $|\boldsymbol{x}\rangle$ and $|\boldsymbol{y}\rangle$ be defined as the following superposition of states.

$$|\boldsymbol{x}\rangle=\sum_{j=0}^{2^{n}-1} x_{j}|j\rangle$$

$$|\boldsymbol{y}\rangle=\sum_{k=0}^{2^{n}-1} y_{k}|k\rangle$$

Consider the conversion to $|\boldsymbol{x}\rangle \rightarrow |\boldsymbol{y}\rangle$. The $|\boldsymbol{y}\rangle$ can be converted as follows.

\begin{aligned} |\boldsymbol{y}\rangle&=\sum_{k=0}^{2^{n}-1} y_{k}|k\rangle \\ &=\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \sum_{j=0}^{2^{n}-1} x_{j} \exp \left(i \frac{2 \pi k j}{2^{n}}\right)|k\rangle \\ &=\sum_{j=0}^{2^{n}-1} x_{j}\left(\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \exp \left(i \frac{2 \pi k j}{2^{n}}\right)|k\rangle\right) \end{aligned}

This means that

$$|\boldsymbol{j}\rangle \rightarrow \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \exp \left(i \frac{2 \pi k j}{2^{n}}\right)|k\rangle$$

is the quantum Fourier transform. In general, the $\exp$ part of this

$$W=w^{k j}=\exp \left(i \frac{2 \pi kj}{2^{n}}\right)$$

and this $W$ is written as

$$W^{\dagger} W=W W^{\dagger}=I$$

The quantum Fourier transform is a unitary transform because it satisfies

\begin{aligned} & \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \exp \left(i \frac{2 \pi k j}{2^{n}}\right)|k\rangle \\ &=\frac{1}{\sqrt{2^{n}}} \sum_{k_{1}=0}^{1} \sum_{k_{2}=0}^{1} \cdots \sum_{k_{n}=0}^{1} \exp \left(i \frac{2 \pi j\left(k_{1} k_{2} \cdots k_{n}\right){2}}{2^{n}}\right)|k{1}k_{2} \cdots k_{n}\rangle \\ &=\frac{1}{\sqrt{2^{n}}} \sum_{k_{1}={0}}^1 \sum_{k_{2}=0}^{1} \cdots \sum_{k_{n}=0}^{1} \exp \left(i \cdot 2 \pi j\left(0. k_{1} k_{2} \cdots k_{n}\right){2}\right)|k{1} k_{2} \cdots k_{n}\rangle\\ &=\frac{1}{\sqrt{2^{n}}}\left(\sum_{k_{1}=0}^{1} \exp \left(i \cdot 2 \pi j\left(0. k_{1}\right){2}|k{1}\rangle \right)\right) \otimes\left(\sum_{k_{2}=0}^{1} \exp \left(i \cdot 2 \pi j\left(0.0 k_{2}\right){2} \mid k{2}\rangle\right)\right) \otimes \cdots\\ & \cdots \otimes \left(\sum_{k_{n}=0}^{1} \exp (i \cdot 2 \pi j(0. \underbrace{0 \cdots 0 k_{n}}{n})|k{n}\rangle\right) \end{aligned}

Here, $(\cdots)_2$ indicates that it is in binary notation. In addition, the kets are represented in binary as $k_1,k_2, \cdots k_n$ from the left. Next, expand $\displaystyle \Sigma$.

\begin{aligned} &\frac{1}{\sqrt{2^{n}}}\left(|0\rangle + \exp \left(i \cdot 2 \pi j (0.1 \right)_{2}|1\rangle\right) \otimes \left(|0\rangle + \exp \left(i \cdot 2 \pi j \left(0.01 \right)_{2}|1\rangle\right) \right) \otimes \cdots \\ &\cdots \otimes \left(|0\rangle + \exp \left(i \cdot 2 \pi j (0.0 \cdots 1 \right)_{2}|1\rangle\right) \end{aligned}

Now, in binary notation, as $|j\rangle = |j_{1}j_{2}\cdots j_n\rangle$, we have the following.

\begin{aligned} &\exp\left(2 \pi j(0.1)_{2}\right)=\exp\left(2 \pi\left(j_{1} j_{2} \cdots j_{n-1}. j_{n}\right)_{2}\right)=\exp\left(2 \pi\left(0. j_{n}\right)_{2}\right) \\ &\exp\left(2 \pi j(0.01)_{2}\right)=\exp\left(2 \pi\left(j_{1} j_{2} \cdots j_{n-2} . j_{n-1} j_{n}\right)_{2}\right)=\exp\left(2 \pi\left(0.j_{n-1} j_{n}\right)_{2}\right) \\ &\vdots \\ &\exp\left(2 \pi_{j}(0.0 \cdots 01)_{2}\right)=\exp\left(2 \pi\left(0 . j_{2} \cdots j_{n-1} j_{n}\right)_{2}\right)\\ &\exp\left(2 \pi_{j}(0.0 \cdots 01)_{2}\right)=\exp\left(2 \pi\left(0 . j_{1} j_{2} \cdots j_{n-1} j_{n}\right)_{2}\right) \end{aligned}