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 .
google colaboratory
- 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} $$
Is the point that we don’t have to consider the integer part over $2$\pi$?
If we proceed with the calculation, we get
$$ \begin{aligned} &\frac{1}{\sqrt{2^{n}}}\left( |0\rangle + \exp \left(i \cdot 2 \pi \cdot 0.j_{n} \right)|1\rangle \right) \otimes \left(|0\rangle + \exp \left(i \ \cdot 2 \pi \cdot 0.j_{n-1}j_{n} \right)|1\rangle \right) \otimes \cdots\\ &\cdots \otimes \left(|0\rangle + \exp \left(i \cdot 2 \pi \cdot 0.j_1j_2\cdots j_n \right)|1\rangle \right) \cdots (1) \end{aligned} $$
This is the same as This expression, as shown on the qiskit website, is
$$ \frac{1}{\sqrt{N}}\left(|0\rangle+e^{\frac{2 \pi i}{2} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{2}} x}|1\rangle\right) \otimes \ldots \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{n-1}} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{n} x}}|1\rangle\right) \cdots (2) $$
This is the same as The next point is how to represent this in a quantum circuit.
The first circuit
The first circuit is an adamantine gate. The first circuit is an adamantine gate, which acts on the state $j$ as follows. $$ H\left|j\right\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(\frac{2 \pi i}{2} j\right)|1\rangle\right) $$
The second circuit
The second circuit is the Control-Rotation circuit, which changes the eigenvalues according to the control bits, and is a gate that changes the phase of the CNOT gate to any $(2^{-x})$.
$$ \begin{gathered} C R O T_{k}\left|0 x_{j}\right\rangle=\left|0 x_{j}\right\rangle \\ C R O T_{k}\left|1 x_{j}\right\rangle=\exp \left(\frac{2 \pi i}{2^{k}} x_{j}\right)\left|1 x_{j}\right\rangle \end{gathered} $$
Expressed as a matrix, it looks like this.
$$ U R O T_{k}=\left[\begin{array}{lc} 1 & 0 \\ 0 & \exp \left(\frac{2 \pi i}{2^{k}}\right) \end{array}\right] $$
Quantum circuits
This is a descent, but let’s apply the Adamar and CROT gates to two qubits.
$$ \begin{aligned} CROT_2 \cdot H_1\left|j_1j_2\right\rangle&=CROT_2 \left( \frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(\frac{2 \pi i}{2} j_1 \right)|1\rangle\right)\otimes|j_2\rangle\right) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(\frac{2 \pi i}{2}j_1 + \frac{2 \pi i}{2^2} j_2 \right)|1\rangle\otimes|j_2\rangle\right) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_1 + i \cdot 2 \pi \cdot 0.0j_2 \right)|1\rangle\otimes|j_2\rangle\right) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_1j_2 \right)|1\rangle\otimes|j_2\rangle\right) \\ \end{aligned} $$
If we extend this to $n$ bits and also generalize the CROT gate, we get
$$ \begin{aligned} CROT_n \cdots CROT_2 \cdot H_1\left|j_1j_2\cdots j_n\right\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_1j_2\cdots j_n \right)|1\rangle\otimes|j_2j_3\cdots j_n\rangle\right) \\ \end{aligned} $$
The first term in this equation is similar to the last term in equation (1). In the above, we made the control qubit the first qubit, but we can change this to the second and third qubits to perform the same action.
If we then apply the Adamant gate to the second qubit and the CROT gate with the control bit as the second qubit, we get
$$ \begin{aligned} & CROT_n \cdots CROT_2 \cdot H_2 \cdot \frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_1j_2\cdots j_n \right)|1\rangle\otimes|j_2j_3\cdots j_n\rangle\right) \\ &=\frac{1}{\sqrt{2}}\left(|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_1j_2\cdots j_n \right)|1\rangle\otimes|0\rangle+\exp \left(i \cdot 2 \pi \cdot 0.j_2\cdots j_n \right)|1\rangle\otimes|j_3j_4\cdots j_n\rangle\right) \cdots (3)\\ \end{aligned} $$
Now, if $x=j_1j_2\cdots j_n$, then
$$ i \cdot 2 \pi \cdot 0.j_1j_2j_3\cdots j_n = \frac{2\pi i}{2^n}x $$ $$ i \cdot 2 \pi \cdot 0.j_2j_3\cdots j_n = \frac{2\pi i}{2^{n-1}}x $$ $$ i \cdot 2 \pi \cdot 0.j_3\cdots j_n = \frac{2\pi i}{2^{n-2}}x $$
So, furthering the calculation in (3), we can write
$$ \frac{1}{\sqrt{2^n}}\left(|0\rangle+e^{\frac{2 \pi i}{2^n} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{n-1}} x}|1\rangle\right) \otimes \ldots \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2^{2}} x}|1\rangle\right) \otimes\left(|0\rangle+e^{\frac{2 \pi i}{2} x}|1\rangle\right) $$
Multiply by Compared to Equation (2), the order of the qubits is inverted, but this is not a big problem since we can just apply the swap gate.
In other words, the quantum Fourier transform can be realized by combining the adamantine and CROT gates.
Creating a quantum Fourier transform circuit using qiskit
Let’s try to create a circuit that simulates a quantum Fourier transform using qiskit. We will start by applying an adamantine gate to the rightmost bit. Finally, we need to apply a swap gate to exchange the states of the bits.
qc = QuantumCircuit(3)
qc.h(2)
qc.draw('mpl')
qc.cp(pi/2, 1, 2) # CROT from qubit 1 to qubit 2
qc.draw('mpl')
qc.cp(pi/4, 0, 2) # CROT from qubit 0 to qubit 2
qc.draw('mpl')
qc.h(1)
qc.cp(pi/2, 0, 1) # CROT from qubit 0 to qubit 1
qc.h(0)
qc.draw('mpl')
qc.swap(0,2)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \\ \frac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \\ \tfrac{1}{\sqrt{8}} \end{bmatrix} $
Check the case of two qubits with qiskit
Let’s check the quantum Fourier transform in two qubits with qiskit to see if the hand-calculated results are correct.
from numpy import pi
from qiskit import QuantumCircuit, transpile, assemble, Aer, IBMQ, execute
from qiskit.providers.ibmq import least_busy
from qiskit.tools.monitor import job_monitor
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit_textbook.tools import array_to_latex
For 00.
$$ \begin{aligned} \left|00\right\rangle &=\frac{1}{\sqrt{2^{2}}} \sum_{k=0}^{3} \exp \left(i \frac{2 pi k j}{2^{2}}\right)|k\rangle \\ &=\frac{1}{\sqrt{2^{2}}}\sum_{k=0}^{3} |k\rangle \\ &=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle \right) \end{aligned} $$
qc = QuantumCircuit(2)
qc.h(1)
qc.cp(pi/2, 0, 1)
qc.h(0)
qc.swap(0,1)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2} \\ \tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix} $
and they match.
For 01.
$$ \begin{aligned} |01\rangle &=\frac{1}{\sqrt{2^{2}}} \sum_{k=1}^{3} exp \left(i \frac{2 \pi}{2^{2}} k\right)|k\rangle \\ &=\frac{1}{2}\left(|00\rangle+i|01\rangle-|10\rangle-i|11\rangle \right) \end{aligned} $$
qc = QuantumCircuit(2)
qc.x(0)
qc.h(1)
qc.cp(pi/2, 0, 1)
qc.h(0)
qc.swap(0,1)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2}i \\ -\tfrac{1}{2} \\ -\frac{1}{2}i \end{bmatrix} $
and they are in agreement.
For 10.
$$ \begin{aligned} |10\rangle &=\frac{1}{\sqrt{2^{2}}} \sum_{k=0}^{3} \exp \left(i \frac{2 \pi \cdot 2}{2^{2}} k\right)|k\rangle \\ &=\frac{1}{2} \sum_{k=0}^{3} \exp (i \pi k)|k\rangle \\ &=\frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right) \end{aligned} $$
qc = QuantumCircuit(2)
qc.x(1)
qc.h(1)
qc.cp(pi/2, 0, 1)
qc.h(0)
qc.swap(0,1)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{2} \\ -\tfrac{1}{2} \\ \tfrac{1}{2} \\ -\frac{1}{2} \end{bmatrix} $
and this is also consistent.
For 11.
$$ \begin{aligned} |11 \mid &=\frac{1}{\sqrt{2^{2}}} \sum_{k=0}^{3} \exp \left(i \frac{2 \pi}{2^{2}} 3 k\right)|k\rangle \\ &=\frac{1}{2}\sum_{k=0}^{3}\exp \left(i\frac{3}{2}\pi k\right)|k\rangle \\ &=\frac{1}{2}\left(|00\rangle-i|01\rangle-|10\rangle+i|11\rangle \right) \end{aligned} $$
qc = QuantumCircuit(2)
qc.x(0)
qc.x(1)
qc.h(1)
qc.cp(pi/2, 0, 1)
qc.h(0)
qc.swap(0,1)
qc.draw('mpl')
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\text{Statevector} = ")
$\displaystyle \\text{Statevector} = \begin{bmatrix} \tfrac{1}{2} \\ -\tfrac{1}{2}i \\ -\tfrac{1}{2} \\ \tfrac{1}{2}i \end{bmatrix} $
From the above, we can confirm the result of the manual calculation.
About the amount of calculation
I have been referring to Dr. Shimada’s book, Quantum Computing: From Basic Algorithms to Quantum Machine Learning , the computational complexity of FFT is $O((\log N)^2)$ and that of quantum Fourier transform is $O(N\log N)$. It looks like the quantum Fourier transform is faster, but considering the effort of execution and measurement, the quantum Fourier transform does not necessarily have an advantage. Nevertheless, the person who first thought of this is a genius. I can only admire it.