計資中心電子報C&INC E-paper

作者：許曄琳 / 臺大物理系博士後研究

---

本文以教學導向方式介紹量子傅立葉轉換(quantum Fourier Transform, QFT)。在實現線路前，先證明QFT為酉算符，奠定其可實作性。接著將QFT分解為Hadamard閘和受控相位閘組成，以IBM Qiskit建構與模擬。

 

簡介

量子傅立葉轉換(quantum Fourier Transform, QFT)是量子演算法中一個重要的基石。由於其與古典的離散傅立葉轉換(discrete Fourier Transform)數學結構一樣，QFT可揭示潛藏的週期，且可做基底轉換從而簡化計算。其主要的應用主要有三種：

1. 相位估測(quantum phase estimation)：一些演算法的核心，例如Harrow-Hassidim-Lloyd (HHL, 以量子線路近似求解限性方程組的演算法)，量子計算化學中的變分量子演算法(variational quantum eigensolver)和幅度估測(quantum amplitude estimation)，都需要對某個酉算符(unitary operator)求其本徵相位(eigenphase)。由於該相位是以$2\pi$為週期的，因此可利用QFT可以將這個隱含的相位轉成二進位數字。
2. 找出阿貝爾隱含子群問題(Abelian hidden subgroup problems)中的週期與子群，例如Shor的因數分解與離散對數（discrete log）。

量子傅立葉轉換定義與量子線路

在$n$個量子位元所組成的一組正交歸一(orthonormal)基底$\left| \left. \ 0 \right\rangle \right.\ ,\ldots,\left| \left. \ N - 1 \right\rangle \right.\$，其中$N \equiv 2^{n}$，對某一量子態$\mid j\rangle$的QFT定義如下：

 

$$\begin{matrix} & \left| \left. \ j \right\rangle \right.\ \longmapsto \frac{1}{\sqrt{N}}\sum_{k = 0}^{N - 1}e^{\frac{2\pi ijk}{N}}\left| \left. \ k \right\rangle \right.\ = \mathbf{F}\left| \left. \ j \right\rangle \right.\ . & & \end{matrix}$$	(1)
$$\begin{matrix} & \mathbf{F}\text{≡}\frac{1}{\sqrt{N}}\sum_{j = 0}^{N - 1}{\sum_{k = 0}^{N - 1}e^{2\pi ijk/N}}\left| \left. \ k \right\rangle \right.\ \left. \ \left\langle j \right.\ \right|. & & \end{matrix}$$	(2)

 

若要將QFT算符$\mathbf{F}$實現，必須先證明$\mathbf{F}$為酉算符，亦宜$\mathbf{F}^{\dagger}\mathbf{F} = \mathbf{I}$, 其中$\mathbf{F}^{\dagger}$為複共軛(complex conjugate)算符，$\mathbf{I}$為單位矩陣(identity matrix)。證明如下：

 

$$\begin{matrix} & \mathbf{F}^{\dagger}\mathbf{F}\text{=}\frac{1}{N}\sum_{j' = 0}^{N - 1}\sum_{k' = 0}^{N - 1}\sum_{j = 0}^{N - 1}{\sum_{k = 0}^{N - 1}e^{2\pi i(jk - j'k')/N}}\left| \left. \ j' \right\rangle \right.\ \left. \ \left\langle j \right.\ \right|\delta_{k'k} & & \end{matrix}$$	(3-1)
$$\begin{matrix} & \text{=}\frac{1}{N}\sum_{j' = 0}^{N - 1}\sum_{k' = 0}^{N - 1}\sum_{k = 0}^{N - 1}e^{2\pi i(j - j')k'/N}\left| \left. \ j' \right\rangle \right.\ \left. \ \left\langle j \right.\ \right| & & \end{matrix}$$	(3-2)
$$\begin{matrix} & \text{=}\sum_{j' = 0}^{N - 1}{\sum_{j' = 0}^{N - 1}{\left| \left. \ j' \right\rangle \right.\ \left. \ \left\langle j \right.\ \right|\delta_{j'j}}} = \sum_{j = 0}^{N - 1}{\left| \left. \ j \right\rangle \right.\ \left. \ \left\langle j \right.\ \right|} = \mathbf{I} & & \end{matrix}$$	(3-3)

 

其中$\delta_{k'k}$為克羅內乘積(Kronecker product)。

由於量子態$\mid j\rangle$的組成是二位元 ($\mid j\rangle ＝ \mid j_{1}j_{2}\ldots j_{n}\rangle$, ${j}_{l} \in \{ 0,1\}$)，可定義下列符號來簡化計算：

 

$$\begin{array}{ccc}\hfill \hfill & \hfill 0.j_l{j}_{l+1}\dots j_m\mathrm{\text{≡}}{j}_l\mathrm{\text{/2+}}{j}_{l+1}\mathrm{\text{/}}{2}^2\mathrm{\text{+…++}}{j}_m\mathrm{\text{/}}{2}^{m-l+1}\hfill & \hfill \hfill \end{array}$$

(4)

 

經由一些代數，式(1)可以改寫如下式：

 

$\left| \left. \ j \right\rangle \right.\ \longmapsto \frac{1}{2^{\frac{n}{2}}}\left( \left| \left. \ 0 \right\rangle + e^{2\pi i0.j_{n}}\left| \left. \ 1 \right\rangle \right.\ \right.\ \right)\left( \left| \left. \ 0 \right\rangle + e^{2\pi i0.j_{n - 1}j_{n}}\left| \left. \ 1 \right\rangle \right.\ \right.\ \right)\text{…}\left( \left| \left. \ 0 \right\rangle + e^{2\pi i0.j_{1}j_{2}\ldots j_{n}}\left| \left. \ 1 \right\rangle \right.\ \right.\ \right)$

(5)

 

式(5)中每一個量子位元可用受控相位閘 (controlled phase gate) $\mathbf{R}_{k}$(如下式)來設計：

 

$$\begin{matrix} & \mathbf{R}_{k}\text{≡}\begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^{k}} \end{pmatrix} & & \end{matrix}$$

(6)

 

當$k = 1$時，$\mathbf{R}_{1}$為Hadamard gate $\mathbf{H}$。由式(5)可將QFT的線路實現如Fig. 1。

Fig. 1: 由式(5)所實現的QFT量子線路。(摘錄自[1]的Fig. 5.1。)

程式範例

我們以三個量子位元作為程式範例，在Fig. 2(a)-(f)逐步解說如何以python的IBM qiskit library建構出QFT的量子線路。

Fig. 2(a): 環境設定程式碼

Fig. 2(b): 建構3個量子位元。

 

Fig. 2(c): 在IBM Qiskit的架構中，其位元標號順序為$\mid q_{n}q_{n - 1}\ldots q_{1}\rangle$，與式(5)所使用的標示相反。亦即，$q_{2}$為式(5)中的$j_{1}$。

Fig. 2(d): 建構Fig. 1中的$j_{1}$位元。$P$為Qiskit中的相位閘(phase gate)，而與連接著兩個位元的相位閘則是式(6)的受控相位閘門所。

Fig. 2(e): 建構Fig. 1中的$j_{2}$與$j_{3}$位元。

Fig. 2(f): 因為Qiskit位元標號順序與式(5)相反，使用交換閘 (SWAP gate) 將$q_{2}$與$q_{0}$對調。

以$\mid j = 5\rangle = \mid 101\rangle$為例，如Fig. 3(a)，$q_{0}$的理論值為$\left( \left| \left. \ 0 \right\rangle \right.\ + e^{2\pi i\left( \frac{5}{2^{3}} \right)}\left| \left. \ 1 \right\rangle \right.\ \right)$，$q_{1} = \left( \left| \left. \ 0 \right\rangle \right.\ + i\left| \left. \ 1 \right\rangle \right.\ \right)$，$q_{2} = \left( \left| \left. \ 0 \right\rangle \right.\ - \left| \left. \ 1 \right\rangle \right.\ \right)$，Bloche sphere的對應位置如Fig. 3(b)。QFT結果如公式(7)：

 

$\left| \left. \ j＝5 \right\rangle \right.\ \longmapsto \frac{1}{\sqrt{8}}\left( \left| \left. \ 0 \right\rangle \right.\ - \frac{1 + i}{\sqrt{2}}\left| \left. \ 1 \right\rangle \right.\ + i\left| \left. \ 2 \right\rangle \right.\ + \frac{1 - i}{\sqrt{2}}\left| \left. \ 3 \right\rangle \right.\ - \left| \left. \ 4 \right\rangle \right.\ + \frac{1 + i}{\sqrt{2}}\left| \left. \ 5 \right\rangle \right.\ - i\left| \left. \ 6 \right\rangle \right.\ + \frac{- 1 + i}{\sqrt{2}}\left| \left. \ 7 \right\rangle \right.\ \right)$

(7)

 

由於式(7)的振幅都是$1/\sqrt{8}$，量測每個量子態基底都會是單一的$1/8$，如Fig. 4，而其中相位的資訊並不能在量測結果中顯示出來。

Fig. 3(a): 以$\mid j = 5\rangle$為例，每一個位元的QFT理論數值。

Fig. 3(b): 以$\mid j = 5\rangle$為例，每一個位元的QFT理論數值在Bloche sphere上的位置。

Fig. 4: 對Fig. 3(a)量子線路做測量的結果。

結語

由本文簡單的QFT範例可見，每個量子位元都需要與其他位元互相作用。在一般在硬體實現上，這意味QFT往往是「電路很深」的程序，容易受雜訊干擾。精確的QFT在$n$個量子位元上需要$\Theta(n^{2})$個量子閘（大量長距離的受控相位閘），實作時還常因拓撲受限而加入SWAP 閘，使深度進一步增加。

需要強調的是，QFT並非把古典離散傅立葉轉換（DFT）加速的量子版本，它的核心角色在把相位資訊轉成可讀位元的（QPE），以及切換到傅立葉基底來簡化某些演算法。典型的應用場景包含量子化學的本徵值估計、HHL 線性方程求解和Shor’s 因數分解等。

參考資料

[1] Nielsen, M.A., & Chuang, I.L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press.