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

# Deutsch 演算法（下）在上篇文章中，我們簡要介紹 Deutsch 演算法在做什麼，這篇文章我們要逐步解析電路中每一個環節在做什麼。如果讀者對於以下數學證明沒有興趣，可以直接跳至下一篇文章。回到上篇提到以下這電路圖，我們將這電路圖拆成四個部分，分別是 $|\psi_0\rangle$ 到 $|\psi_4\rangle$，接著我們一步一步用數學描述這四個部分發生什麼事。

## $|\psi_0\rangle$ 最一開始的狀態，即圖中的 $|\psi_0\rangle$ 為： \begin{split} |\psi_0\rangle&=|0\rangle |1\rangle \end{split} ## $|\psi_1\rangle$ 接著兩個 qubits 都經過 H gate 操作，先回顧 H gate 的作用： \begin{split} H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\\ H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 因此這兩個 qubits 的狀態變為： \begin{split} |\psi_1\rangle&=H|0\rangle \otimes H|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$ 都長得一樣。 ## $|\psi_2\rangle$、$|\psi_3\rangle$ 與 $|\psi_4\rangle$

接下來的操作，會因為你要判斷的函數不同，而有不同的狀態。從上一篇文章可以得知 $f(x)$ 不管實際長什麼樣子，他的輸入與輸出只會有四種情況：所以我們接著會分成四種情況做分別討論。建議你先準備個白紙與鉛筆，靜下心，喝杯咖啡後，專心把以下四個情況一次看完看懂，就解脫了。 ### 情況一函數是： \begin{split} f(0)=f(1)=0 \end{split} 在經過 $U_f$ 之前，$|\psi_1\rangle$ 是四種狀態的疊加態： \begin{split} |\psi_1\rangle=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 所以我們會再分成四種狀態做討論，之後的案例就會直接給出結果，留給讀者在紙上推敲 #### 當 $|\psi_1\rangle = |00\rangle$ 經過 $U_f$ 操作後，第一個 qubits 還是 $|0\rangle$，第二個 qubits 則為 $0\oplus f(0)$，在這裡，$f(0)=0$，所以 $0\oplus f(0)=0\oplus 0=0$，因此輸出 $|00\rangle$ #### 當 $|\psi_1\rangle = |01\rangle$ 同理，第一個 qubits 還是 $|0\rangle$，第二個 qubits 則為 $1\oplus f(0)=1\oplus 0=1$，因此輸出 $|01\rangle$ #### 當 $|\psi_1\rangle = |10\rangle$ 第一個 qubits 是 $|1\rangle$，第二個 qubits 會是 $0\oplus f(1)=0\oplus 0=0$，因此輸出 $|10\rangle$ #### 當 $|\psi_1\rangle = |11\rangle$ 第一個 qubits 是 $|1\rangle$，第二個 qubits 會是 $1\oplus f(1)=1\oplus 0=1$，因此輸出 $|11\rangle$ 綜合上述四種情況，得出： \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|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} 所以就是沒變，第一個 qubits 經過 H gate 操作後，就變成 \begin{split} |\psi_3\rangle&=H|\psi_2\rangle \\ &=H[\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)] \\ &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\ &=|0\rangle \end{split} 對 $|\psi\rangle$ 測量後得出 $0$，代表這函數是 "constant"。 ### 情況二函數是： \begin{split} f(0)=f(1)=1 \end{split} 經過 $U_f$ 操作後，得出 \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|00\rangle-|01\rangle+|10\rangle-|11\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$ ### 情況三前面兩個情況都是 constant function，接下來要討論的兩種情況都是 balanced function，計算上會稍微難一點點點。情況三的函數是： \begin{split} f(0)=0 \\ f(1)=1 \end{split} 經過 $U_f$ 操作後，得出 \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|00\rangle-|01\rangle+|10\rangle-|11\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\rangle$ 相比，會發現 $|10\rangle$ 和 $|11\rangle$ 前面的正負號（相位）剛好相法，這正負號是 DJ 演算法判斷函數是哪一種的關鍵。經過整理後： \begin{split} |\psi_2\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以，第一個 qubit 經過 H gate 操作後 \begin{split} |\psi_3\rangle&=H|\psi_2\rangle\\ &=H[\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)]\\ &=|1\rangle \end{split} 測量後得到 $1$，這函數是 balanced。 ### 情況四撐住啊，最後一個案例了 \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。