07 - 量子傅立葉轉換 (Quantum Fourier Transform)[QFT]

功用

傅立葉轉換可以幹嘛 : … 待續

原理&實作

首先,複習一下什麼是二進位

一個二進位數字 101122+021+120101\rightarrow1\cdot2^2+ 0\cdot2^1 + 1\cdot2^0

我們描述一個狀態時 111|111\rangle 有時 0,1 太多太麻煩,會寫成 7|7\rangle

反之同理 k|k\rangle 也可以寫成 k1k2k3...kn|k_1k_2k_3...k_n\ranglekxk_x 們和二進位一樣,不是 0 就是 1

另外描述小數點也是一樣,在二進位中的 0.0110.011 也就是 021+122+123\rightarrow 0\cdot2^{-1}+ 1\cdot2^{-2} + 1\cdot2^{-3}

接下來,就輪到傅立葉了@@

FNF_N 為離散傅立葉轉換(Discrete Fourier Transform)的函式 :

FNj=1Nk=0N1wNjkkF_N|j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}w_{N}^{jk}|k\rangle

(wN=e2πi/N)(w_{N} = e^{2\pi i/N})

改寫一下就成了

FNj=1Nk=0N1e2πijk/NkF_N|j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle

有 n 個 bit,就能夠表達出 (2n2^n) 種狀態,因此 N=2nN=2^n

FNj=12nk=0N1e2πijk/2nkF_N|j\rangle = \frac{1}{\sqrt{2^n}}\sum_{k=0}^{N-1}e^{2\pi ijk/2^{n}}|k\rangle

一開始有提到 k=k1k2k3...kn|k\rangle = |k_1k_2k_3...k_n\rangle

k=a=1nka2na\Rightarrow k = \sum_{a=1}^{n} k_{a}\cdot2^{n-a}

k/2n=a=1nka2a\Rightarrow k/{2^n} = \sum_{a=1}^{n} k_{a}\cdot2^{-a}

一樣塞進方程式中

FNj=12nk=0N1e2πij(a=1nka2a)k1k2k3...knF_N|j\rangle = \frac{1}{\sqrt{2^n}}\sum_{k=0}^{N-1}e^{2\pi ij(\sum_{a=1}^{n} k_{a}\cdot2^{-a})}|k_1k_2k_3...k_n\rangle

這個符號 :a=1n\bigotimes_{a=1}^{n} ,代表從第 11 顆一直串到第 nn

FNj=12n k1,k2,...,kn{0,1} a=1ne2πijka/2akaF_N|j\rangle = \frac{1}{\sqrt{2^n}}\ \sum_{k_1,k_2,...,k_n\in \{0,1\}}\ \bigotimes_{a=1}^{n}e^{2\pi ijk_{a}/2^a}|k_a\rangle

FNj=12na=1n (ka{0,1}e2πijka/2aka)F_N|j\rangle = \frac{1}{\sqrt{2^n}}\bigotimes_{a=1}^{n}\ (\sum_{k_a\in\{0,1\}}e^{2\pi ijk_{a}/2^a}|k_a\rangle)

FNj=12na=1n (e2πij0/2a0+e2πij1/2a1)F_N|j\rangle = \frac{1}{\sqrt{2^n}}\bigotimes_{a=1}^{n}\ ( e^{2\pi ij0/2^a}|0\rangle + e^{2\pi ij1/2^a}|1\rangle)

最後,該消的消一消,大功告成:

FNj=a=1n 12(0+e2πij/2a1)F_N|j\rangle = \bigotimes_{a=1}^{n}\ \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi ij/2^a}|1\rangle)

假設我們有 3 個 qubit (可表達232^3種狀態) 帶進來 (N=8)(N=8)

F8j1j2j3=12(0+e2πi0.j31)12(0+e2πi0.j2j31)12(0+e2πi0.j1j2j31)F_8|j_1j_2j_3\rangle = \frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i0.j_3}|1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i0.j_2j_3}|1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i0.j_1j_2j_3}|1\rangle)

0.j1j2j30.j_1j_2j_3 … ?

就是一開始說的小數點 0.j1j2j3j121+j222+j3230.j_1j_2j_3 \rightarrow j_1\cdot2^{-1} + j_2\cdot2^{-2} + j_3\cdot2^{-3}

為了旋轉他,這時候還需要一個 Controlled-RsR_s Gates, 才能夠實作出來。

Rs=[100e2πi/2s]R_s = \begin{bmatrix}1&0\\0&e^{2\pi i/2^{s}}\end{bmatrix}


R1=Z=[1001]R_1 = Z = \begin{bmatrix}1&0\\0&-1\end{bmatrix}R2=S=[100i]R_2 = S = \begin{bmatrix}1&0\\0&i\end{bmatrix}R3=T=[100eiπ/4]R_3 = T = \begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix}

實作方法:

Code:
量子傅立葉轉換

Reference:

要注意的是,做完 Hadamard 和 Controlled-RsR_s Gates 之後必須將順序對調 (反序),因為一開始為了公式好推,定義時 k=k1k2k3...kn|k\rangle = |k_1k_2k_3...k_n\rangle 就跟平常我們所認知的相反了 XD"