量子傅立葉轉換（下） | EntangleTech 量子教育平台

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

QFT 電路圖

在[量子傅立葉轉換（上）](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 的輸出量子態，如下圖所示：

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

QFT 電路圖

這就是完整個 QFT 電路圖。