

訊號經 DFT 轉換後成頻率

C 大調為期一秒的波形

C 大調為期 0.05 秒的波形

C 大調的頻譜分析
這就是所有筆資料的平均值\begin{split} y_1 = \frac{1}{\sqrt{N}} (a_0+a_1\omega+a_2\omega^2 \cdots + a_{N-1}\omega^{N-1}) \end{split}
可以看出其 y0 與 y1 的 phase 項差一個 omega\begin{split} y_2 = \frac{1}{\sqrt{N}} (a_0+a_1\omega^2+a_2\omega^4 \cdots + a_{N-1}\omega^{2(N-1)}) \end{split}
可以看出其 y2 與 y0 的 phase 項相差 2 倍將上式寫成矩陣 \begin{align}\tag{2} \begin{bmatrix} y_0 \\ y_1 \\ \vdots\\ y_{N-1} \end{bmatrix}= \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)^2} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots\\ a_{N-1} \end{bmatrix} \end{align} 這種視覺上看起來很舒適的矩陣,對於電腦而言也需要 $O(N^2)$ 步,不過不必灰心,有種演算法稱作 fast Fourier transform(FFT)可以將複雜度降低到 $O(N\log N)$,不過這不是今天的重點,我們就不針對這演算法做介紹。 ## 量子電腦的解法 從 $(2)$ 式中我們看到中間 $N\times N$ 矩陣是一個 unitary 的矩陣,這代表我們可以用量子邏輯閘組合出這個矩陣,以做到加速的效果,這就是量子傅立葉轉換(QFT)。 對應到量子電路,$(2)$ 式告訴我們這電路的初始態為 \begin{align} |a\rangle= \begin{bmatrix} a_0 \\ a_1 \\ \vdots\\ a_{N-1} \end{bmatrix}= a_0|0\rangle+a_1|1\rangle+a_2|2\rangle+\cdots+a_{N-1}|N-1\rangle= \sum_{j=0}^{N-1} a_j|j\rangle \end{align} 其中 \begin{align} |0\rangle= \begin{bmatrix} 1 \\ 0 \\ 0 \\ \vdots \end{bmatrix} , |1\rangle= \begin{bmatrix} 0 \\ 1 \\ 0 \\ \vdots \end{bmatrix} , |2\rangle= \begin{bmatrix} 0 \\ 0 \\ 1 \\ \vdots \end{bmatrix} \end{align} 經過中間 $N\times N$ 矩陣或說量子邏輯閘操作後,電路輸出 \begin{align} |y\rangle= \begin{bmatrix} y_0 \\ y_1 \\ \vdots\\ y_{N-1} \end{bmatrix}= y_0|0\rangle+y_1|1\rangle+y_2|2\rangle+\cdots+y_{N-1}|N-1\rangle=\sum_{j=0}^{N-1} y_k|k\rangle \end{align} 這時我們就稱 $|y\rangle$ 是 $|\psi\rangle$ 的量子傅立葉轉換。結合 $(1)$ 式: \begin{align}\tag{1} y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} a_j e^{i \frac{2\pi}{N} jk} \end{align} 以下這條數學式就是 QFT 要達成的事情: \begin{align} QFT|a\rangle=|y\rangle=\sum_{k=0}^{N-1} y_k|k\rangle= \frac{1}{\sqrt N}\sum_{k=0}^{N-1}\sum_{j=0}^{N-1}a_je^{i\frac{2\pi}{N}jk}|k\rangle \end{align} 不難看出 \begin{align}\tag{3} |j\rangle \rightarrow\frac{1}{\sqrt N}\sum_{k=0}^{N-1}\omega^{jk}|k\rangle \end{align} \begin{align}\tag{4} y_k=\frac{1}{\sqrt 2}\sum_{j=0}^{N-1}a_j \omega^{jk} \end{align} 在 DFT 中,$N$ 對應到資料筆數,在量子電腦中,$N=2^n$,$n$ 是 qubit 數,接著我們來看 QFT 運作起來的效果是什麼: ### 一個 qubit 我們先從最簡單的系統開始,即只有一個 qubit,即 $n=1$,那 $N=2$,$\omega=e^{i\frac{2\pi}{2}}=e^{i\pi}=-1$,初始態 $|a\rangle=a_0|0\rangle+a_1|1\rangle$
倒數第二句話用到歐拉公式因此從(4)式: \begin{align} y_k&=\frac{1}{\sqrt 2}\sum_{j=0}^{N-1}a_j \omega^{jk} \\ &=\frac{1}{\sqrt 2}[a_0(-1)^{0k}+a_1(-1)^{1k}] \\ &=\frac{1}{\sqrt 2}[a_0+a_1(-1)^k] \end{align} 當電路初始態為 $|a\rangle=|0\rangle$,即 $a_0=1, a_1=0$,上式則為 \begin{align} y_0=y_1=\frac{1}{\sqrt 2} \end{align} 當電路初始態為 $|a\rangle=|1\rangle$,即 $a_0=0, a_1=1$,則為 \begin{align} y_0=\frac{1}{\sqrt 2} \\ y_1=-\frac{1}{\sqrt 2} \end{align} 綜合以上: \begin{align} QFT|0\rangle=\frac{1}{\sqrt 2}(|0\rangle+|1\rangle) \end{align} \begin{align} QFT|1\rangle=\frac{1}{\sqrt 2}(|0\rangle-|1\rangle) \end{align} 有沒有覺得這個哪裡似曾相似,沒錯,就是 H gate 的作用,所以在只有一個 qubit 的時候,QFT 長這樣
n=1 的 QFT 電路圖
如果數學是你的罩門,中間推導可以跳過,直接看電路圖長什麼樣子所以: \begin{align} QFT|j_1j_0\rangle=\frac{1}{\sqrt 4}\sum_{k=0}^3 e^{i2\pi\frac{1}{4}j(2k_1+k_0)}|k_1k_0\rangle \end{align}
因為四式中的 k 是十進制,要從二進制 k1k0 轉回去就是 2k1_k0,同理 j 也是上式接續下去 \begin{align} &=\frac{1}{\sqrt 4}\sum_{k=0}^3 e^{i2\pi\frac{1}{4}j(2k_1+k_0)}|k_1k_0\rangle \\ &= \frac{1}{2}\sum_{k_1=0}^1 e^{i2\pi 2\frac{1}{4}jk_1}|k_1\rangle \otimes \sum_{k_0=0}^1 e^{i2\pi \frac{1}{4}jk_0}|k_0\rangle \\ &= \frac{1}{2}(|0\rangle+e^{i\pi j}|1\rangle) \otimes (|0\rangle+e^{i\pi \frac{1}{2} j}|1\rangle) \\ &=\frac{1}{2}(|0\rangle+e^{i\pi (2j_1+j_0)}|1\rangle) \otimes (|0\rangle+e^{i\pi \frac{1}{2} (2j_1+j_0)}|1\rangle) \\ \end{align} 最後一行第一項可以拆解成 $e^{2i\pi j_1}e^{i\pi j_0}$,當 $j_1=1$ 時 $e^{2i\pi}=1$(當 $j_0=0$ 時也是 $1$),所以可以簡化成 $e^{i\pi j_0}$ \begin{align} &=\frac{1}{2} (|0\rangle+e^{i\pi j_0}|1\rangle) \otimes (|0\rangle+e^{i\pi j_1}e^{\frac{1}{2}i\pi j_0}|1\rangle) \\ &=\frac{1}{2} (|0\rangle+e^{i\pi j_0}|1\rangle) \otimes e^{\frac{1}{2}i\pi j_0} (|0\rangle+e^{i\pi j_1}|1\rangle) \\ &=\frac{1}{2} (|0\rangle+(-1)^{j_0}|1\rangle) \otimes S^{j_0} (|0\rangle+(-1)^{j_1}|1\rangle) \end{align} 如果以上看得眼花撩亂,那就跳過,但注意這個,這邊出現一個新的代數 $S^{j_0}$,他的效果是: \begin{split} \text{當 }j_0=0,S^{j_0}=e^0=I \\ \text{當 }j_0=1,S^{j_0}=e^{\frac{1}{2}\pi i}=S \\ \end{split} 所以他是一個 controlled S gate(CS gate),因此上面結果可以寫成 \begin{split} &=\frac{1}{2} (|0\rangle+(-1)^{j_0}|1\rangle) \otimes S^{j_0} (|0\rangle+(-1)^{j_1}|1\rangle) \\ &= (H\otimes I)CS(I\otimes H)|j_0j_1\rangle \\ &=(H\otimes I)CS(I\otimes H)SWAP|j_1j_0\rangle \end{split} 所以 $n=2$ 的 QFT 電路圖為:
n=2 的 QFT 電路圖
n=3 的 QFT 電路圖
QFT 電路圖
有些教材的電路圖剛好與本圖上下相反,就只要把輸入的順序上下相反就好