---
# System prepended metadata

title: 07 量子傅立葉轉換（下）
tags: [量子演算法（下）]

---

# 量子傅立葉轉換（下）
我們在前面兩篇文章介紹 QFT 為何物，如何運作，這篇我們將來解析 QFT 的電路圖是怎麼推導出來的，推導過程會十分複雜，歡迎有興趣的讀者閱讀，沒興趣的話跳過這篇也不影響後面文章的閱讀（但如果你是致力做這領域研究工作，含著淚也要看完）。

<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/BkZmDwvtJx.svg" 
         alt="QFT" width="110%"/>
    <br>
    <p>QFT 電路圖
    </p>
</div>

在[量子傅立葉轉換（上）](https://www.entangletech.tw/lesson/algorithm-05)中，我們提到 QFT 的作用就是

\begin{align} \tag{1}
|j\rangle\rightarrow \frac{1}{\sqrt N}\sum_{k=0}^{N-1}e^{i\frac{2\pi}{N}jk}|k\rangle
\end{align}

因為電腦是[二進位表示](https://www.entangletech.tw/lesson/basic-algorithm-02)，我們要把 $j$ 表示成

\begin{split}
j&=j_{0}j_{1}\cdots j_{n-2}j_{n-1} \\
&=j_{0}2^{n-1}+j_{1}2^{n-2}+\cdots+j_{n-2} 2^1+j_{n-1}2^0
\end{split}

那我們也可以把 $\frac{j}{N}$ 以二進位做表示（其中 $N=2^n$）

\begin{split}
\frac{j}{N}&=
\frac{j_{0}2^{n-1}+j_{1}2^{n-2}+\cdots+j_{n-2} 2^1+j_{n-1}2^0}{2^n} \\
&=\frac{j_{0}}{2}+\frac{j_{1}}{2^2}+\cdots+\frac{j_{n-2}}{2^{n-1}}+\frac{j_{n-1}}{2^n} \\
&=0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}
\end{split}

同樣地，我們也可以把 $k$ 以二進位表示法做表示

\begin{split}
k&=k_{0}k_{1}\cdots k_{n-2}k_{n-1} \\
&=k_{0}2^{n-1}+k_{1}2^{n-2}+\cdots+k_{n-2} 2^1+k_{n-1}2^0
\end{split}

那式（1）中看起來很煩人的一項 $e^{2\pi ik\frac{j}{N}}$ 可以表示得更煩人：

\begin{split}
e^{2i\pi k\frac{j}{N}} &=
e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})
(k_{0}2^{n-1}+k_{1}2^{n-2}+\cdots+k_{n-2} 2^1+k_{n-1}2^0)}\\
&=e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{0}2^{n-1}} \times 
e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})k_{1}2^{n-2}}\times\cdots \\
& \qquad \times 
e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})k_{n-2} 2^1} \times e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})k_{n-1} 2^0}
\end{split}

接著我們把 $2^{n-1}$、$2^{n-2}$... 丟進左邊括號中，就會變成（注意小數點的位置）：

\begin{align}
=e^{2i\pi(j_{0}j_{1}\cdots j_{n-2}.j_{n-1})k_{0}}\times 
e^{2i\pi(j_{0}j_{1}\cdots j_{n-3}.j_{n-2}j_{n-1})k_{1}}\cdots \\
\times 
e^{2i\pi(j_{0}.j_{1}\cdots j_{n-2}j_{n-1})k_{n-2}}\times e^{2i\pi(0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})k_{n-1}} \tag{2}
\end{align}

我們先看第一項，經過運算後第一項可以簡寫成：

\begin{align} 
e^{2i\pi(j_{0}j_{1}\cdots j_{n-2}.j_{n-1})k_{0}}&=
e^{2i\pi(j_{0}2^{n-2}+j_{1}2^{n-3}\cdots j_{n-2}2^0+j_{n-1} 2^{-1})k_{0}} \\
&=e^{2i\pi j_{0}2^{n-2}k_{0}}e^{2i\pi j_{1}2^{n-3}k_{0}}\cdots e^{2i\pi j_{n-2}2^{n-2}k_{0}}e^{2i\pi j_{n-1} 2^{-1}k_{0}} \\
&=1\times 1\times\cdots \times 1\times e^{2i\pi j_{n-1}2^{-1}k_{0}} \\
&=e^{2i\pi 0.j_{n-1}k_{0}}
\end{align}

因為前面幾項要嘛是 $e^0=1$ 要嘛就是 $e^{i2\pi N}=1$（$N$ 是正整數）。因此（2）式可以簡寫成

\begin{split}
e^{2i\pi k\frac{j}{N}}=
e^{2i\pi (0.j_{n-1}) k_{0}}e^{2i\pi (0.j_{n-2}j_{n-1}) k_{1}}\cdots 
e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) k_{n-2}}e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{n-1}}
\end{split}

插入（1）式得到

\begin{split}
|j\rangle &\rightarrow \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2i\pi k\frac{j}{N}} |k\rangle \\
&=\frac{1}{\sqrt N} \sum_{k=0}^{N-1} 
e^{2i\pi (0.j_{n-1}) k_{0}}
e^{2i\pi (0.j_{n-2}j_{n-1}) k_1}\cdots 
e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) k_{n-2}}
e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{n-1}} |k\rangle
\end{split}

上述這式子中的加總是針對二進位數字 $k$ 作家總，而 $k$ 就只會是 $0$ 和 $1$，因此上式變成

\begin{split}
\frac{1}{\sqrt N}\sum_{k_{n-1}=0}^1 \cdots \sum_{k_{0}=0}^1 
e^{2i\pi (0.j_{n-1}) k_{0}}
e^{2i\pi (0.j_{n-2}j_{n-1}) k_{1}}\cdots 
e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) k_{n-2}}
e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{n-1}} |k_{0}\cdots k_{n-1}\rangle
\end{split}

其中 $|k_{0}\cdots k_{n-1}\rangle$ 可以寫成 $|k_{0}\rangle\cdots |k_{n-1}\rangle$，因此上式可以改寫成

\begin{split}
\frac{1}{\sqrt N}\sum_{k_{0}=0}^1 \cdots \sum_{k_{n-1}=0}^1 
e^{2i\pi (0.j_{n-1}) k_{0}}|k_{0}\rangle 
e^{2i\pi (0.j_{n-1} j_{n-2}) k_{1}}|k_{1}\rangle \cdots e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) k_{n-2}} |k_{n-2}\rangle 
e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{n-1}} |k_{n-1}\rangle
\end{split}

繼續改寫：

\begin{align} \tag{3}
\frac{1}{\sqrt N} 
\sum_{k_{0}=0}^1 
e^{2i\pi (0.j_{n-1}) k_{0}}|k_{0}\rangle 
\sum_{k_{1}=0}^1 
e^{2i\pi (0.j_{n-1}j_{n-2}) k_{1}}|k_{1}\rangle \cdots \sum_{k_{n-2}=0}^1 
e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) k_{n-2}} |k_{n-2}\rangle \sum_{k_{n-1}=0}^1 
e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1}) k_{n-1}} |k_{n-1}\rangle
\end{align}

當 $k_{0}=0$ 時，$e^{2i\pi (0.j_{n-1}) k_{0}}=e^0=1$，其他項也是：

\begin{split}
\frac{1}{\sqrt N}  
(|0\rangle+e^{2i\pi (0.j_{n-1}) }|1\rangle) (|0\rangle+e^{2i\pi (0.j_{n-2}j_{n-1} )}|1\rangle) \cdots (|0\rangle+ e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1}) } |1\rangle) 
(|0\rangle+ e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})} |1\rangle)
\end{split}

最後，$\sqrt{N}=\sqrt{2^n}$，然後我們就能寫出 QFT 的二進位表示法：

\begin{align} \tag{4}
\frac{1}{\sqrt 2}  
(|0\rangle+e^{2i\pi (0.j_{n-1}) }|1\rangle) 
\frac{1}{\sqrt 2}
(|0\rangle+e^{2i\pi (0.j_{n-2}j_{n-1})}|1\rangle)\cdots \frac{1}{\sqrt 2}
(|0\rangle+ e^{2i\pi (0.j_{1}\cdots j_{n-2}j_{n-1})} |1\rangle) 
\frac{1}{\sqrt 2}
(|0\rangle+ e^{2i\pi (0.j_{0}j_{1}\cdots j_{n-2}j_{n-1})} |1\rangle)
\end{align}

接著我們來看看如何透過 H gate 與 controlled rotation gate 組合出（3）式。我們先從 (4) 式中最右邊的項開始，我們對 $|j_{0}\rangle$ 做 H gate 操作

\begin{split}
H|j_{0}\rangle &=\frac{1}{\sqrt 2}[|0\rangle+(-1)^{j_{0}}|1\rangle] =\frac{1}{\sqrt 2}[|0\rangle+(e^{i\pi})^{j_{0}}|1\rangle] \\
&=\frac{1}{\sqrt 2}[|0\rangle+e^{i\pi \frac{2}{2}j_{0}}|1\rangle] \\ &
= \frac{1}{\sqrt 2}(|0\rangle+e^{2i\pi (0.j_{0})}|1\rangle) 
\end{split}

接著我們引入 $R_2$ gate，controlled qubit 為第 $2$ 個 qubit（$j_{1}$），target qubit 則為第 $1$ 個 qubit。所以當 $j_{1}$ 為 $1$ 時（$j_0$），$j_{0}$ 會乘上 $e^{i\frac{1}{2}\pi}$：

\begin{split}
\frac{1}{\sqrt 2}(|0\rangle+e^{2i\pi (0.j_{0})}|1\rangle) &\rightarrow  
\frac{1}{\sqrt 2}(|0\rangle+(e^{2i\pi (0.j_{0})})(e^{i\frac{1}{4}\pi})^{j_{1}} |1\rangle) \\
&=\frac{1}{\sqrt 2}(|0\rangle +e^{2i\pi (0.j_{0})}e^{2i\pi (0.0j_{1})}|1\rangle) \\
&=\frac{1}{\sqrt 2}(|0\rangle+e^{2i\pi (0.j_{0}j_{1})}|1\rangle)
\end{split}

同樣地，放入 $R_3$ gate，上式會變成

\begin{split}
\frac{1}{\sqrt 2}(|0\rangle+e^{2i\pi 0.j_{0}j_{1}j_{2}}|1\rangle)
\end{split}

以此類推，要組合出（4）式中最右邊的項，要引入多個 $R_n$ gate，最後上式就能變得跟（4）式中最右邊的項一樣

\begin{split}
\frac{1}{\sqrt 2}(|0\rangle+e^{2i\pi 0.j_{0}j_{1}j_{2}\cdots j_{n-1}}|1\rangle)
\end{split}

這就是下圖第一個 qubit 最後會產生的量子態，就是（4）式中的最幼項。以此類推我們可以推導出每個 qubit 的輸出量子態，如下圖所示：

<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/H1icPDwYyx.svg" 
         alt="QFT" width="150%"/>
    <br>
    <p>
    </p>
</div>

仔細將輸出結果與（3）式中對應的 $|k\rangle$ 比較，發現與我們預期 QFT 輸出態（見下圖或是本篇的第一張圖），在順序上剛好相反，所以我們加上數個 SWAP gate 將結果順序導正：

<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/BkZmDwvtJx.svg" 
         alt="QFT" width="110%"/>
    <br>
    <p>QFT 電路圖
    </p>
</div>

這就是完整個 QFT 電路圖。

