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

# Deutsch-Jozsa Algorithm（上）前面介紹的 Deutsch 演算法只能解決單變數之函數問題（就兩張撲克牌），Jozsa 將 Deutsch 的想法延伸到可以應用在多變數之函數問題（多張撲克牌），即耳熟能詳的 DJ 演算法。 ## 要解決什麼問題？與上一節類似，只是問題變成多變數函數，一樣要判斷函數是 constant 還是 balanced function，或是用撲克牌的例子，判斷多張撲克牌會是下咧兩種情況的哪種： 1. 所有的牌都是紅色或是黑色 2. 有一半的牌是紅色，另外一半是黑色舉個例子，比方說判斷有兩個變數的函數（兩個變數代表可以表示四張撲克牌）： \begin{split} f(x_0,x_1)=x_0\oplus x_1 \end{split} 這函數所有的輸入與輸出為： \begin{split} f(0,0)=0\\ f(0,1)=1\\ f(1,0)=1\\ f(1,1)=0 \end{split} 不是全部的輸出都一樣，而是有一半的輸出是 $0$，另外一半輸出是 $1$，因此這函數是 balance function。 ## 經典電腦的解法 ### 第一種解法如果是你眼前的電腦或手機，跟上節一樣，就是所有的可能的輸入都算過一遍後，比較函數輸出結果來判斷函數的類型。當函數有 $n$ 個變數時，就要計算 $2^n$ 種可能，並進行$\frac{(2^n-1)2^n}{2}$ 次比較。以上面提到兩變數 function 為例， \begin{split} \text{Step 1: }&f(0,0)=a \\ \text{Step 2: }&f(0,1)=b \\ \text{Step 3: }&f(1,0)=c \\ \text{Step 4: }&f(1,1)=d \\ \text{Step 5: }& a=b? \\ \text{Step 6: }& a=c? \\ \text{Step 7: }& a=d? \\ \text{Step 8: }& b=c? \\ \text{Step 9: }& b=d? \\ \text{Step 10: }& c=d? \\ \end{split} 總共需要要 4 次計算和 6 次比較，經典電腦總共要執行 10 步才能告訴你這函數是 balanced 還是 constant。 ### 第二種解法不過以上是最笨的做法，但也是最保證不會出錯。另一種解法就是我們在 Deutsch 演算法中提到撲克牌的例子，檢查一半數目的撲克牌後再多檢查一張牌，寫成數學式就是，當函數有 $n$ 個變數，就要計算 $\frac{2^n}{2}+1=2^{n-1}+1$ 次。以前面的函數為例子，原本要算 4 次，現在僅需 3 次。所以，經典演算法的複雜度為 $O(2^n)$。 ## 量子電腦的解法如果今天問題是單變數，像是 $f(x)=x$，電路會長得跟 Deutsch 演算法一樣

當問題是多變數時，像是 $f(x_0,x_1)=x_0\oplus x_1$，就是簡單地把上圖延伸成

如果測量結果（$|m_0m_1m_2...m_{n-1}\rangle$）都是 0，表示這函數是 constant function；如果不是，代表這函數是 balanced function。不管函數有幾個變量時，量子電腦都只需要計算 1 次，因此演算法複雜度為 $O(1)$，相比經典電腦，當變數越多時，量子電腦所謂的加速作用會越明顯

藍色和橘色都是經典電腦，藍色是透過最笨的方式，橘色則是經第二種解法；灰色則為量子電腦。當函數的變數來到 5 個時，經典電腦最少也需要計算 17 次，而量子電腦僅需 1 次，大大減少計算所需時間

## 範例回到前面提的例子： \begin{split} f(x_0,x_1)=x_0\oplus x_1 \end{split} 這函數有兩個變數，所以要用 3 個 qubits，DJ 演算法基本會長這樣：

後面還有測量動作，這邊沒有秀出來

中間的 $U_f$ 會長什麼樣子呢？跟 Deutsch 演算法的思路一樣，要先知道經過 $U_f$ 操作後各 qubit 的狀態為何。我們知道前面 2 個 qubits 的狀態不會變，第 3 個 qubit 的狀態會變成： \begin{split} y\oplus f(x)&=y\oplus (x_0\oplus x_1)\\ &=(y\oplus x_0)\oplus x_1 \end{split} 先看第一項 $y\oplus x_0$，將表格寫出來後長這樣 \begin{array}{|c|c|} \hline \text{輸入} &U_f\text{ 輸出} & U_f\text{ 輸出}\\ \hline x_0 \quad y & x_0 & y\oplus x_0 \\ \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} 給你點時間想想什麼樣的 gate 能產生如同表格中呈現的效果。你可以看到只有輸入 $(x_0,y)$ 為 $(1,0)$ 和 $(1,1)$，狀態（輸出）才會改變。沒錯！就是 CNOT gate，所以 $U_f$ 有一部分長這樣：

緊接著是第二項 $[(y\oplus x_0)]\oplus x_1$ \begin{array}{|c|c|} \hline \text{輸入} & \text{輸入} &U_f\text{ 輸出} & U_f\text{ 輸出}\\ \hline y\oplus x_0 & x_1 & y\oplus x_0 & [y\oplus x_0]\oplus x_1 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 0\\ \hline \end{array} 老掉牙了，這很明顯也是 CNOT gate，所以完整電路長這樣

簡單自己算一下，或是用 Qiskit composer 操作，這測量結果不是 $|00\rangle$，所以這函數是 balanced function。 ## 演算法的應用現在，給你點時間想想這演算法能應用在生活上什麼地方。沒錯！沒有，不過這不代表這演算法沒有任何價值，事實上它在量子計算發展的初期提供一個很好的模型，展示量子電腦如何“加速”計算，比經典電腦更快。這邊作者特別介紹，比 DJ 演算法更快的算法，只要看到多變數的 function，先猜 "balance function" 就對了，你會發現在多變數的情況下，要湊出 "constant function" 並不容易。