Deutsch 演算法 | EntangleTech 量子教育平台

# Deutsch Algorithm 英國物理學家 David Deutsch 在 1985 年提出 Deutsch 演算法，他的學生 Richard Jozsa 將老師的想法延伸，於 1992 年提出 Deutsch-Jozsa 演算法，簡稱 DJ 演算法，這期，我們將先介紹 Deutsch 演算法，在下一篇我們把概念延伸，介紹 DJ 演算法。 ## 要解決什麼問題？ Deutsch 想要解決一項數學問題，假使有一個函數（function），可以輸入 0 或 1，函數會輸出 0 或 1 \begin{split} f:\{0,1\}\rightarrow\{0,1\}\ \end{split} 如果不管輸入 0 還是 1，函數都輸出 0，這函數我們歸類在 "constant function"，同理，如果都輸出 1，也被歸類在此。

如果輸入 0 則輸出 0，輸入 1 則輸出 1，或是相反，輸入 0 得出 1，輸入 1 得出 0，這種函數我們歸類在 "balance constant"。假設有一個函數是 \begin{split} f(x)=x \end{split} 輸入 0 會得出 0，輸入 1 會得出 1，按照前面所述，這函數是 balance function。 Deutsch 演算法，或說是 DJ 演算法就是應用在此，判定一個函數是 constant 還是 balance。 ## 經典電腦解法同樣的問題，你眼前的電腦或手機會怎麼解這問題呢？很簡單，就是先代入 0 得出結果 1，在代入 1 得出結果 2，比較兩個結果一不一樣，一樣則這函數是 constant，不一樣則為 balance。 \begin{split} \text{Step 1: }&f(0)=a \\ \text{Step 2: }&f(1)=b \\ \text{Step 3: } &\text{if }a = b \text{ constant} \\ &\text{if }a \neq b \text{ balance} \end{split} 總共需要兩個步驟，加上最後比較結果的話，共 3 個步驟，那量子電腦的解法呢？ ## 量子電腦解法

先別看到圖就怕，等等會一步一步帶您解析，Deutsch 提供的解法如上圖，準備兩個 qubits，一個是 0，一個是 1，兩個都做 H gate 後，再做 $U_f$ 操作，這邊先不細談 $U_f$ 究竟長什麼樣子，但經過這一番操作後，第二個 qubits 輸出的值會是 $y$ 與 $f(x)$ 的二進位加法，最後對第一個 qubit 做 H gate 後測量，如果量測出來的值是 0，這函數為 constant，反之，是 1 的話就是 balance。因此，量子電腦的解法只需要一個步驟就能得知函數是哪一種。接下來，我們將細談這演算法怎麼運作 ## 量子演算法解析最一開始的狀態，即圖中的 $|\psi_0\rangle$ 為： \begin{split} |\psi_0\rangle=|0\rangle |1\rangle \end{split} 兩個都經過 H gate 操作後： \begin{split} |\psi_1\rangle&=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 不管今天你要判讀的函數長什麼樣子，$|\psi_0\rangle$ 和 $|\psi_1\rangle$ 都長得一樣，接下來的操作，會因為你代入的函數不同，而有不同的狀態，所以接下來，會分成 4 個 case 做討論（在此例中，函數也只有會 4 種）建議你先準備個白紙與鉛筆，靜下心，喝杯咖啡後，專心把以下四個案例一次看完看懂，就解脫了。 ### 案例一函數是： \begin{split} f(0)=f(1)=0 \end{split} 在 $|\psi_1\rangle$ 的時候，系統是四種狀態的疊加態，所以我們會先分成四種狀態做討論，之後的案例就會直接給出結果，留給讀者在紙上推敲 #### 00 第一種狀態就是 $|00\rangle$，經過 $U_f$ 操作後，第一個 qubits 還是 $|0\rangle$，第二個 qubits 則為 $0\oplus f(0)=0\oplus 0=0$，因此輸出 $|00\rangle$ #### 01 同理，第一個 qubits 還是 $|0\rangle$，第二個 qubits 則為 $1\oplus f(0)=1\oplus 0=1$，因此輸出 $|01\rangle$ #### 10 第一個 qubits 是 $|1\rangle$，第二個 qubits 會是 $0\oplus f(1)=0\oplus 0=0$，因此輸出 $|10\rangle$ #### 11 第一個 qubits 是 $|1\rangle$，第二個 qubits 會是 $1\oplus f(1)=1\oplus 0=1$，因此輸出 $|11\rangle$ 綜合上述，得出 \begin{split} |\psi_2\rangle&=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以就是沒變，第一個 qubits 經過 H gate 操作後，就變成 \begin{split} |\psi_3\rangle=|0\rangle \end{split} 根據前述，測量出 0 就代表函數是 constant。 ### 案例二函數是： \begin{split} f(0)=f(1)=1 \end{split} 經過 $U_f$ 操作後，得出 \begin{split} |\psi_2\rangle&=\frac{1}{2}(|01\rangle-|00\rangle+|11\rangle-|10\rangle) \\ &= \frac{1}{2}(-|00\rangle+|01\rangle-|10\rangle+|11\rangle)\\ &=-\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 會發現這和 $|\psi_1\rangle$ 差一個負號，經過整理後得出 \begin{split} |\psi_2\rangle=-\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以測量第一個 qubits，得出來依然是 $|0\rangle$ ### 案例三函數是 \begin{split} f(0)=0 \\ f(1)=1 \end{split} 經過 $U_f$ 操作後，得出 \begin{split} |\psi_2\rangle&=\frac{1}{2}(|00\rangle-|01\rangle+|11\rangle-|10\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle) \end{split} 與 $|\psi_1$ 相比，會發現 $|10\rangle$ 和 $|11\rangle$ 前面的正負符號（相位）剛好相法，這也是這演算法判斷函數是哪一種的關鍵。經過整理後： \begin{split} |\psi_2\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以，第一個 qubit 測量出的狀態為 \begin{split} |\psi_3\rangle=|1\rangle \end{split} 此函數為 balance。 ### 案例四撐住啊，最後一個案例了 \begin{split} f(0)=1 \\ f(1)=0 \end{split} 其實結果就跟案例三一樣，但差了一個負號 \begin{split} |\psi_2\rangle&=\frac{1}{2}(|01\rangle-|00\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{2}(-|00\rangle+|01\rangle+|10\rangle-|11\rangle) \\ &=-\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle) \\ &=-\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以最後測量出也是 1。 ## 範例恭喜你細心看完以上詳細的解析，可是，我們還是沒有提 $U_f$ 究竟是什麼，因此我們就有最一開始提到的函數作為範例 \begin{split} f(x)=x \end{split} 根據前面介紹，我們知道 Deutsch 演算法最基本會長這樣

而我們要 gate 湊出 $U_f$ 的功能，因此我們要先畫出一個表格，輸入什麼到 $U_f$，$U_f$ 會輸出什麼：

現在，給你幾分鐘想想什麼樣的 gate 能做到一樣的功能... 沒錯就是 CNOT gate，回想一下 CNOT gate。因此，完整的演算法長這樣：

Deutsch 演算法只有 2 個 qubits，僅能判斷只有一個位元的函數，在下一篇我們會介紹 Jozsa 提出的演算法，將他老師的想法延伸應用到多位元的函數。

本文章採用創用 CC「姓名標示-相同方式分享 4.0 國際」授權條款