---
# System prepended metadata

title: 02 Deutsch algorithm （下）
tags: [量子演算法（下）]

---

# Deutsch 演算法（下）

在上篇文章中，我們簡要介紹 Deutsch 演算法在做什麼，這篇文章我們要逐步解析電路中每一個環節在做什麼。如果讀者對於以下數學證明沒有興趣，可以直接跳至下一篇文章。

回到上篇提到以下這電路圖，我們將這電路圖拆成四個部分，分別是 $|\psi_0\rangle$ 到 $|\psi_4\rangle$，接著我們一步一步用數學描述這四個部分發生什麼事。

<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/SkWg5JuJ1x.svg" alt="Deutsch circuit" width="100%"/>
    <br>
    <p>
    </p>
</div>

## $|\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$ 

<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/SkWg5JuJ1x.svg" alt="Deutsch circuit" width="100%"/>
    <br>
    <p>
    </p>
</div>

接下來的操作，會因為你要判斷的函數不同，而有不同的狀態。從上一篇文章可以得知 $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。