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

# Deutsch Algorithm（上）英國物理學家 David Deutsch 在 1985 年提出 Deutsch 演算法，後來數學家 Richard Jozsa 將想法延伸，於 1992 年提出 [Deutsch-Jozsa 演算法](https://royalsocietypublishing.org/doi/10.1098/rspa.1992.0167)，簡稱 DJ 演算法，在這篇文章中，我們將先介紹 Deutsch 演算法。

David Deutsch

圖片來自 Wiki

假設我手中有一組 52 張撲克牌，我手上的撲克牌只會是下列兩種情況： 1. 所有的牌都是紅色或是黑色 2. 有一半的牌是紅色，另外一半是黑色

給你 52 張撲克牌，要你想個方法，能夠快速地知道這組撲克牌的顏色分不是第一種情況：全部都是黑色或紅色，或是第二種情況：有一半是紅色，另一半是黑色

其中第一種情況稱作 "constant"，第二種情況稱作 "balanced"，現在要請你判斷我手中的撲克牌會是這兩種情況的哪一種。這時候你從這組撲克牌中拿起第一張牌，今天如果運氣很好，你翻起來的第一張牌與第二張牌是不同的顏色，那這組撲克牌一定會是 "balanced"；如果不幸的話，你需要看 $\frac{52}{2}+1=27$ 張牌，假設前面 26 張牌都是黑色，如果第 27 張牌是黑色，那全部的牌都是黑色，如果是紅色，那這組牌是 "baanced"。以上這形象的舉例就是 Deutsch 與 DJ 演算法要解決的問題，如何用更快的方式判斷這組撲克牌是 "constant" 還是 "balanced"。 ## 要解決什麼問題？剛剛的撲克牌問題可以寫成以下這數學形式： \begin{split} f(x)=y \end{split} 其中 $x$ 代表第 $x$ 張撲克牌，$y$ 代表撲克牌的顏色，$y=0$ 代表撲克牌是黑色，$y=1$ 則為紅色。將 $x$ 代入函數（function）$f$，函數會輸出該張撲克牌的顏色。為了方便起見，我們將問題限縮到只有兩張撲克牌，所以 $x$ 只會是 0 或 1。

資工人習慣從 0 開始計數，第 0 張就是平常習慣說第一張的意思

當我們輸入 0 或是 1 給這個函數 $f$ 時， $f$ 會輸出 0 或是 1，寫成數學形式就是： \begin{split} f:\{0,1\}\rightarrow\{0,1\}\ \end{split} 我們姑且不論這函數究竟長什麼樣子，這函數的輸入與輸出結果有以下四種

單變數二進位函數的四種可能，前面兩種稱作 constant，後面兩種稱作 balanced

其中，不管 $x$ 是 0 還是 1，$f$ 都輸出 0 或是 1（代表兩張撲克牌都是黑色或紅色），這種函數（或說情況）就是 "constant"；相反地，輸入 0，函數輸出 0，輸入 1，函數輸出 1，或是另一種情形，輸入 0，函數輸出 1，輸入 0，函數輸出 1，都代表這兩張撲克牌，有一張是黑色，另外一張是紅色，這兩種情況都稱作 "balanced"。現在，假設這函數 $f$ 是： \begin{split} f(x)=x \end{split} 當 $x$ 是 0 ，$f(x)$ 輸出 0，$x$ 是 1 的話，輸出 $y$ 是 1，所以這函數屬於 "balanced" function。Deutsch 演算法與 DJ 演算法就是要解決這問題：判斷一個函數屬於 "constant" 還是 "balanced"。 ## 經典電腦的解法同樣的問題，你眼前的電腦或手機會怎麼解這問題呢？很簡單，就跟前面撲克牌的舉例一樣，一張一張翻起來看，電腦也是，先將 $x$ 代入 $0$ 給該函數，函數得出第一個結果，接著再將 $x$ 代入 $1$ 給函數得出第二個結果，然後比較兩個結果，如果數字一樣，這函數就是 constant，不一樣的話，就代表這函數式 balanced： \begin{split} \text{步驟 1: }&f(0)=a \\ \text{步驟 2: }&f(1)=b \\ \text{步驟 3: } &\text{如果 }a = b \text{：constant} \\ &\text{如果 }a \neq b \text{：balanced} \end{split} 這計算過程共需要兩個步驟，加上最後結果比較，總共要 3 個步驟才能告訴我們這函數是哪一種。那換成用量子電腦會如何呢？ ## 量子電腦的解法這問題交給量子電腦的話，僅需透過以下電路，計算一次就能告訴我們答案。

Deutsch algorithm 電路圖

注意，從這邊開始，y 是指圖中第二個 qubit 在 U 之前的量子態，而非前面函數輸出的結果（撲克牌的顏色）

先別看到圖就怕。首先，準備兩個 qubits，其中第二個 qubit 做 X gate 操作變成 $|1\rangle$，接著兩個 qubits 都做 H gate 操作，做 $U_f$ 操作，這邊先不細談 $U_f$ 究竟長什麼樣子，僅需知道 $U_f$ 會輸出什麼結果。經過 $U_f$ 的操作後，第一個 qubit 的狀態不變，但第二個 qubit 的狀態會是 $y$ 與 $f(x)$ 的二進位加法（$y\oplus f(x)$）。最後，對第一個 qubit 做 H gate 後測量，如果量測出來的值是 0，代表這函數為 "constant"，反之，是 1 的話就是 "balanced"。因此，量子電腦的解法只需要一個步驟就能得知函數是哪一種。有興趣了解這電路中每一步怎麼運作，可以看下一篇文章。 ## 範例最後，我們用一個簡單的例子帶你使用 DJ 演算法，同時能更了解 $U_f$ 是什麼，回到最一開始舉例的函數： \begin{split} f(x)=x \end{split} 量子電腦會如何判斷這函數是屬於哪一種。從前面的介紹，我們知道 Deutsch 演算法最基本會長這樣：

要完善這電路，我們就必須知道 $U_f$ 要用哪種 gate 組成，所以我們要先知道 $U_f$ 會輸出什麼？要回答這問題，就要畫出下列真值表。 \begin{array}{|c|c|} \hline \text{輸入} &U_f\text{ 輸出} & U_f\text{ 輸出}\\ \hline x \quad y & x & y\oplus f(x) \\ \hline 0\quad 0 & 0 & 0 \\ \hline 0\quad 1 & 0 & 1 \\ \hline 1\quad 0 & 1 & 1\\ \hline 1\quad 1 & 1 & 0\\ \hline \end{array} 如果你看得懂以上表格，可以跳過這段話。因為兩個 qubits（分別是表格中的 $x$ 與 $y$）都經過 H gate 操作，所以 qubit 要嘛是 0 要嘛就是 1，這樣就有四種組合。經過 $U_f$ 操作後，$x$ 還是 $x$ 所以不變，但 $y$ 變成 $y\oplus f(x)$。以第三行為例： \begin{split} y\oplus f(x)=0 \oplus f(1)=0 \oplus (1)=1 \end{split} 同理，其他行也是這樣完成。現在，給你幾分鐘想想或找找，哪個 quantum gate 的行為與表格中的輸入與輸出一樣。沒錯！就是 CNOT gate，回想一下 CNOT gate 的作用： \begin{array}{|c|c|} \hline \text{Input} & \text{Output} \\ \hline A\quad B & A \quad B \\ \hline 0\quad 0 & 0\quad 0 \\ \hline 0\quad 1 & 0\quad 1 \\ \hline 1\quad 0 & 1\quad 1\\ \hline 1\quad 1 & 1\quad 0\\ \hline \end{array} 因此，對於這函數，完整的 DJ 演算法長這樣：

可以根據在[量子計算入門（上）](https://www.entangletech.tw/lesson/basic-algorithm-16)所學的，算算看這電路會輸出什麼，會發現第一個 qubit 經過最後 H gate 操作後會是 $|1\rangle$，代表這函數是 "balanced"。 Deutsch 演算法只有 2 個 qubits，僅能判斷只有一個位元的函數，也就是兩張撲克牌，在下下篇文章我們會將問題延伸到多張撲克牌，看 DJ 演算法是如何解這問題。