$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$
Quantum Fourier Transform¶
First created in September 2018
Fourier Transformation - Classical¶
A recap on Fourier Transform:
$\displaystyle{f(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}F(\Omega)~e^{i\Omega t} d\Omega}\quad\ldots~$Time Domain
$\displaystyle{F(\Omega)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty f(t)~e^{-i\Omega t} dt}\quad\ldots~$Frequency Domain
Both $f(t)$ and $F(\Omega)$ are complex functions.
The above two symmetrical equations represent the same wave in time and frequency domains respectively. Wave in this context can be any quantity with a variation in time. If the integrals are bounded by an interval symmetrical around zero, e.g. $-\frac{T}{2}$ to $\frac{T}{2}$, the wave is periodic with period $T$.
The Fourier transform relates the function's time domain, shown in red, to the function's frequency domain, shown in blue. The component frequencies, spread across the frequency spectrum, are represented as peaks in the frequency domain.
In short, all frequencies at one time gives you harmony (red), and one frequency at all time gives you resonance (blue).
Fourier Transformation - Quantum¶
Fourier Transformation in quantum (discrete) form:
$\displaystyle y_k={1\over\sqrt N}\sum_{j=0}^{N-1}x_j\omega_n^{jk},~~~ \text{where }N=2^n,~~k\in[0,N-1],~~\text{and }\omega_n=e^{2\pi i/N}~$ ($N^\mathrm{th}$ root of unity, for equation $z^N=1$).
Comparing with $\displaystyle{f(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}F(\Omega)~e^{i\Omega t} d\Omega}$, you may identify these associations: $\displaystyle k\sim t,~~y_k\sim f(t),~~j\sim\Omega,~~x_j\sim F(\Omega),~~\omega_n^{jk}=e^{jk\cdot 2\pi i/2^n}\sim e^{\Omega t\cdot i} .$
This form translates to $\Ket y=F_N\Ket x$, where
$j,k\in[0,N-1],~~ \Ket y=[y_k]^T,~~ \Ket x=[x_j]^T,~~ F_N={1\over\sqrt N}\left[\omega_n^{jk}\right] ={1\over\sqrt N} \begin{bmatrix} 1&1&1&1&\ldots&1\\ 1&\omega_n&\omega_n^2&\omega_n^3&\ldots&\omega_n^{N-1}\\ 1&\omega_n^2&\omega_n^4&\omega_n^6&\ldots&\omega_n^{2(N-1)}\\ 1&\omega_n^3&\omega_n^6&\omega_n^9&\ldots&\omega_n^{3(N-1)}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega_n^{N-1}&\omega_n^{2(N-1)}&\omega_n^{3(N-1)}&\ldots&\omega_n^{(N-1)(N-1)}\\ \end{bmatrix} .$
Note: Since indexing range is $[0,N-1]$, the $0^\mathrm{th}$ is the first, and $(N-1)^\mathrm{th}$ the last.
Imagin each of the columns of $F_N$ is an increasingly faster phase change, and $\Ket x$ is a vector of "frequencies" strength, then $F_N\Ket x$ is to add all frequencies into a combined wave $\Ket y$ (harmony). "Playing" $\Ket y$ from top to bottom will see a wave in time.
On the other hand, $F_N^{-1}$ is a progression in time left to right (like a music score), and $\Ket y$ is like a "modulation" wave with time running top to bottom, so $F_N^{-1}\Ket y$ picks out the "melody row" that is most similar to the "$y$ wave" and make it strongest (resonance).
$\Ket y=F_N\Ket x,~~\Ket x=F_N^{-1}\Ket y.$
Analysis¶
A useful relationship here: Each row and column adds up to zero, except the first.
Proof: $\displaystyle j\in[1,N-1],~~ \omega_n^j\ne 1,~~ \omega_n^0=\omega_n^N=1,~~ \omega_n^{Nj}=1,~~{\omega_n^{Nj}-1\over\omega_n^j-1} =\sum_{k=0}^{N-1}\omega_n^{jk} =0.~~$ The first row with $j=0$ would yield $N$. (Same for each column.)
Let us define $\displaystyle\Ket{\xi_j}=\Rsr N\sum_{k=0}^{N-1}\omega_n^{jk}\Ket k,~~$ which is the $j^\mathrm{th}$ column of $F_N$.
We have
$\displaystyle F_N^{-1}\Ket{\xi_j} ={1\over N} \begin{bmatrix} 1&1&1&1&\ldots&1\\ 1&\omega_n^{-1}&\omega_n^{-2}&\omega_n^{-3}&\ldots&\omega_n^{-(N-1)}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega_n^{-j}&\omega_n^{-2j}&\omega_n^{-3j}&\ldots&\omega_n^{-(N-1)j}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega_n^{-(N-1)}&\omega_n^{-2(N-1)}&\omega_n^{-3(N-1)}&\ldots&\omega_n^{-(N-1)(N-1)}\\ \end{bmatrix} \begin{bmatrix}1\\\omega_n^j\\\vdots\\\omega_n^{jk}\\\vdots\\\omega_n^{j(N-1)}\end{bmatrix} =\Ket j .$
Note: After the multiplication, the $j^\mathrm{th}$ row adds up to $N$ and all other rows adds up to zero.
This is very useful.
If you have a set of multiple qubits in superposition, each state would have an increasing phase of regular interval, e.g. $\Ket0,e^\theta\Ket1,e^{2\theta}\Ket2,\ldots,e^{(N-1)\theta}\Ket{N-1}$, an application of $F_N^{-1}$ will pick out the column that closely matches the phase, and the qubits would identify which one.
As you see, $F_N^{-1}=F_N^\dagger=F_N^*,~~$ so $F_N^{-1}$ is just $F_N$ with all elements conjugated (phases negated).
I will illustrate this idea later in this text.
Examples¶
$n=1,~~N=2,~~\omega_1=e^{2\pi i/2}=-1,~~ F_2 ={1\over\sqrt2}\begin{bmatrix}1&1\\1&\omega_1\end{bmatrix} ={1\over\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}=H.$
$n=2,~~N=4,~~\omega_2=e^{2\pi i/4}=i,~~ F_4 ={1\over\sqrt4} \begin{bmatrix} 1&1&1&1\\ 1&\omega_2&\omega_2^2&\omega_2^3\\ 1&\omega_2^2&\omega_2^4&\omega_2^6\\ 1&\omega_2^3&\omega_2^6&\omega_2^9\\ \end{bmatrix} ={1\over\sqrt4} \begin{bmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i\\ \end{bmatrix} .$
e.g. If $\Ket\psi=\frac{1}{2}(\Ket{0}-i\Ket{1}-\Ket{2}+i\Ket{3}),~F_4^{-1}\Ket\psi=\Ket 3.$ This result indicates that $\Ket\psi$ has a phase change of $\omega_2^3=-i$ between two neighbouring states.
From the above, it is apparent that each row represents a rotation of increasing frequency. For $N=4$, the first row $0$ rotation, second $\pi/2$, third $\pi$ and fourth $3\pi/2$. (It is symmetrical so the columns are doing the same.)
As an exercise, for $n=3,~~N=8,~~\omega_3=e^{2\pi i/8}={1\over\sqrt2}(1+i),$ $F_8={1\over\sqrt8} =\begin{bmatrix} 1&1&1&1&1&1&1&1\\ 1&{1\over\sqrt2}(1+i)&i&{1\over\sqrt2}(-1+i)&-1&{1\over\sqrt2}(-1-i)&-i&{1\over\sqrt2}(1-i)\\ 1&i&-1&-i&1&i&-1&-i\\ 1&{1\over\sqrt2}(-1+i)&-i&{1\over\sqrt2}(1+i)&-1&{1\over\sqrt2}(1-i)&i&{1\over\sqrt2}(-1-i)\\ 1&-1&1&-1&1&-1&1&-1\\ 1&{1\over\sqrt2}(-1-i)&i&{1\over\sqrt2}(1-i)&-1&{1\over\sqrt2}(1+i)&-i&{1\over\sqrt2}(-1+i)\\ 1&-i&-1&i&1&-i&-1&i\\ 1&{1\over\sqrt2}(1-i)&-i&{1\over\sqrt2}(-1-i)&-1&{1\over\sqrt2}(-1+i)&i&{1\over\sqrt2}(1+i)\\ \end{bmatrix} .$
One can tell that two rows are complex conjugate of each other if their row index add up to $N$. e.g. the conjugate of the third row (2) equals to the seventh (6).
Properties¶
$F_N$ is not self-inverse as $F_N^2\ne I.$
$F_N$ is unitary.
Proof: $F_N={1\over\sqrt N}\left[\omega_n^{jk}\right],~~ F_N^\dagger={1\over\sqrt N}\left[(\omega_n^{kj})^*\right],~~ F_N F_N^\dagger ={1\over N}\left[\sum_m\omega_n^{jm}(\omega_n^{km})^*\right] ={1\over N}\left[\sum_m\omega_n^{(j-k)m}\right] .$
When $j\ne k,~\sum_m\omega^{(j-k)m}=0.~~$ When $j=k,~\sum_i\omega^{(j-k)m}=\sum_m1=N.~~ \text{i.e.}\sum_m\omega^{(j-k)m}=\delta_{jk}.~~ \therefore F_N F_N^\dagger=I_N.$
$F_N$ is not Hermitian as $F_N^\dagger\ne F_N.~~$ That said, as $\omega^{jk}=\omega^{kj},~~F_N^T=F_N,~~$ so $F_N^\dagger=\left(F_N^T\right)^*=F_N^* .$
That means $F_N^{-1}=F_N^\dagger=F_N^*,~~$ which is to negate all phases: $\overline{\omega_n}=e^{-2\pi i/2^n}.$
Given $\boxed{\displaystyle y_k={1\over\sqrt N}\sum_{j=0}^{N-1}x_j\omega_n^{jk}~}$ and $\omega^{jk}=\omega^{kj},~~$ we have $\Ket y=F_N\Ket x,~~F_N^{-1}\Ket y=\Ket x,~$ and $\boxed{\displaystyle x_j={1\over\sqrt N}\sum_{k=0}^{N-1}y_k\omega_n^{-jk}~}$.
This makes sense as $\displaystyle y_k ={1\over\sqrt N}\sum_{j=0}^{N-1}\left({1\over\sqrt N}\sum_{k'=0}^{N-1}y_{k'}\omega_n^{-jk'}\right)\omega_n^{jk} ={1\over N}\sum_{k'=0}^{N-1}y_{k'}\left(\sum_{j=0}^{N-1}\omega_n^{-jk'}\omega_n^{jk}\right) ={1\over N}\sum_{k'=0}^{N-1}y_{k'}\left(\sum_{j=0}^{N-1}\omega_n^{j(k-k')}\right) .$
The $\omega_n$ terms will add up to zero when $k\ne k'$, and add up to $N$ when $k=k'$. So $\displaystyle y_k={1\over N}y_kN=y_k.$
Implementation¶
Let us examine the case of $n=2,~~N=4,~~j\in[0,3].~~ F_4 ={1\over\sqrt4} \begin{bmatrix} 1&1&1&1\\ 1&\omega_2&\omega_2^2&\omega_2^3\\ 1&\omega_2^2&\omega_2^4&\omega_2^6\\ 1&\omega_2^3&\omega_2^6&\omega_2^9\\ \end{bmatrix} .$
$F_4\Ket{\xi_j}$ is the $j^\mathrm{th}$ column of $F_4.~~$
So $\displaystyle F_4\Ket{\xi_j} ={1\over\sqrt4}\left(\Ket0+\omega_2^{2j}\Ket1\right)\otimes\left(\Ket0+\omega_2^j\Ket1\right) ={1\over\sqrt4}\sum_{k=0}^3\omega_2^{jk}\Ket k .$
To represent $k$ as individual bits $k_r$, we have $\displaystyle k=\sum_{r=0}^{n-1}k_r2^r.~~$
$\displaystyle F_N\Ket{\xi_j} ={1\over\sqrt N} \left(\Ket0+\omega_n^{j\cdot2^{n-1}}\Ket1\right)\otimes \left(\Ket0+\omega_n^{j\cdot2^{n-2}}\Ket1\right)\otimes\ldots\otimes \left(\Ket0+\omega_n^{j\cdot2}\Ket1\right)\otimes \left(\Ket0+\omega_n^j\Ket1\right) ={1\over\sqrt N}\sum_{k=0}^{N-1}\omega_n^{j\cdot\sum_{r=0}^{n-1}k_r2^r}\Ket k ={1\over\sqrt N}\sum_{k=0}^{N-1}\omega_n^{jk}\Ket k .$
To be more concise, for an $m$-qubit value let us define these:
Binary notation: $q=[q_{m-1}q_{m-2}\ldots q_0]=\sum_{k=0}^{m-1}q_k2^k.~~$ e.g. $[101]=1\cdot 2^2+0\cdot 2+1=5$
Fractional notation: $q\cdot2^{-m}=[0.q_{m-1}q_{m-2}\ldots q_0]=\sum_{k=0}^{m-1}q_k2^{k-m}.~~$ e.g. $[0.101]={1\over2}+{0\over4}+{1\over8}={5\over8}.$
Combined notation: $q\cdot2^{-r}=[q_{m-1}q_{m-2}\ldots q_r~.~q_{r-1}\ldots q_0].$
For an arbitrary value of $q\in[0,N-1)$, since $\omega_n^{q\cdot2^{n-r}}=e^{2\pi i/2^n\cdot q\cdot2^{n-r}}=e^{2\pi i/2^r\cdot q}=\omega_r^q$
$\displaystyle~~ F_N\Ket q ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+\omega_n^{q\cdot2^{n-r}}\Ket1\right) ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+\omega_r^q\Ket1\right) ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+e^{2\pi i~q\cdot2^{-r}}\Ket1\right)$
$\displaystyle ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+e^{2\pi i~[q_{n-1}q_{n-2}\ldots q_r~.~q_{r-1}\ldots q_0]}\Ket1\right) ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+e^{2\pi i~[0~.~q_{r-1}\ldots q_0]}\Ket1\right) .$
Note: The integer part of $q\cdot2^{-r}$ is the number of whole $2\pi$ cycles, and therefore can be ignored.
$\boxed{F_N\Ket q={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+e^{2\pi i~[0~.~q_{r-1}\ldots q_0]}\Ket1\right)}$ $={1\over\sqrt N} \left(\Ket0+e^{2\pi i~[0.q_0]}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i~[0.q_1q_0]}\Ket1\right)\otimes \ldots\otimes \left(\Ket0+e^{2\pi i~[0.q_{n-1}q_{n-2}\ldots q_0]}\Ket1\right) .$
"Gating"¶
So what gates we need to use? For example, the MSB $\left(\Ket0+e^{2\pi i~[0.q_0]}\Ket1\right) =\left\{\begin{matrix} \Ket0+\Ket1&\text{when }q_0=0\\ \Ket0-\Ket1&\text{when }q_0=1\\ \end{matrix}\right. ,~~$ which is an $H$ gate on $q_0$.
The second bit is $\left(\Ket0+e^{2\pi i~[0.q_1q_0]}\Ket1\right) =\left\{\begin{matrix} \Ket0+\Ket1&\text{when }q_1q_0=00\\ \Ket0+i\Ket1&\text{when }q_1q_0=01\\ \Ket0-\Ket1&\text{when }q_1q_0=10\\ \Ket0-i\Ket1&\text{when }q_1q_0=11\\ \end{matrix}\right. ,~~$ which is $cS(q_0,q_1)$ and $H$ on $q_1$.
Likewise, the third bit is $\left(\Ket0+e^{2\pi i~[0.q_2q_1q_0]}\Ket1\right) =\left\{\begin{matrix} \Ket0+\Ket1&\text{when }q_2q_1q_0=000\\ \Ket0+e^{i\pi/4}\Ket1&\text{when }q_2q_1q_0=001\\ \Ket0+e^{i2\pi/4}\Ket1&\text{when }q_2q_1q_0=010\\ \Ket0+e^{i3\pi/4}\Ket1&\text{when }q_2q_1q_0=011\\ \Ket0+e^{i4\pi/4}\Ket1&\text{when }q_2q_1q_0=100\\ \Ket0+e^{i5\pi/4}\Ket1&\text{when }q_2q_1q_0=101\\ \Ket0+e^{i6\pi/4}\Ket1&\text{when }q_2q_1q_0=110\\ \Ket0+e^{i7\pi/4}\Ket1&\text{when }q_2q_1q_0=111\\ \end{matrix}\right. ,$ which is an $cT(q_0,q_2)$, $cS(q_1,q_2)$, and $H$ on $q_2$.
Here in this diagram, $\Ket{x_n}$ is our $q_0$ and $\Ket{x_1}$ is our $q_{n-1}$. The operation starts from $\Ket{x_1}$ or $q_{n-1}$ by applying $R_s$ to $q_r$ successively, where $s$ runs from $1$ to $r+1$, each controlled by $q_{r-s+1}$.
An $R_s$ gate is a phase shift by $2\pi/2^s$, i.e. $e^{2\pi i~[0.\overbrace{0..1}^s]}$ or $R_s=\begin{bmatrix}1&0\\0&e^{2\pi i/2^s}\end{bmatrix}=u_1(2\pi/2^s).$
To illustrate, $R_1$ is a rotation by $\pi$ about the $Z$-axis controlled by $q_r$ itself, which means an $R_1=H$ gate. Similarly $R_2=u_1(\pi/2)$ controlled by $q_{r-1}$, and $R_3=u_1(\pi/4)$ by $q_{r-2}$.
Please note that the phase shift $u_1(\theta) =\begin{bmatrix}1&0\\0&e^{i\theta}\end{bmatrix} =e^{i\theta/2}\begin{bmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{bmatrix} \ne\begin{bmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{bmatrix}$ when dealing with phase measurement.
If you use other shift gates, make sure it is equivalent to a $u_1$, with a $1$ at the left upper corner.
For example, the $\pi/8$ gate $T$ needs to be presented as $\begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix},~~$ not $\begin{bmatrix}e^{-i\pi/8}&0\\0&e^{i\pi/8}\end{bmatrix} .$
| \hspace{1em}Gate ($s$)\hspace{1em} | \hspace{1em}Target\hspace{1em} | \hspace{1em}Control ($r-s+1$)\hspace{1em} | \hspace{1em}Shift\hspace{1em} | \hspace{1em}Similar\hspace{1em} |
|---|---|---|---|---|
| $R_1$ | $q_r$ | $q_r$ | $\pi$ | $H$ |
| $R_2$ | $q_r$ | $q_{r-1}$ | $\pi/2$ | $cu_1(\pi/2)$ |
| $R_3$ | $q_r$ | $q_{r-2}$ | $\pi/4$ | $cu_1(\pi/4)$ |
| $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ |
IMPORTANT: Comparing with $F_N\Ket q ={1\over\sqrt N} \left(\Ket0+e^{2\pi i~[0.q_0]}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i~[0.q_1q_0]}\Ket1\right)\otimes \ldots\otimes \left(\Ket0+e^{2\pi i~[0.q_{n-1}q_{n-2}\ldots q_0]}\Ket1\right),~~$
you may notice that the qubit order is reversed.
The input mapping is $q_{n-1}:x_1,~~q_{n-2}:x_2,~~\ldots,~~q_1:x_{n-1},~~q_0:x_n.$
The output mapping is $q_{n-1}:x_n,~~q_{n-2}:x_{n-1},~~\ldots~~q_1:x_2,~~q_0:x_1.$
Code Section¶
# Initialisation
import sys
sys.path.append('../')
from qtol import *
# Iteration
# Number of qubits
qbNum = 3
# Define the Quantum and Classical Registers
q = QuantumRegister(qbNum)
c = ClassicalRegister(qbNum)
qc = QuantumCircuit(q, c)
# Preparation
# Pick out the third row of F_8 (j=2=[10])
#qc.h(q)
qc.x(q[1])
# Circuit building
qc.h(q[2])
qc.cu1(np.pi/2.0, q[1], q[2])
qc.cu1(np.pi/4.0, q[0], q[2])
qc.h(q[1])
qc.cu1(np.pi/2.0, q[0], q[1])
qc.h(q[0])
# Finalisation
# ...
show_me(qc, q, c, show_latex=True, show_bloch_vector=True, show_histogram=True)
circuit_drawer(qc)
