# 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 演算法一樣

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

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

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

如果測量結果（$|m_0m_1m_2...m_{n-1}\rangle$）都是 0，表示這函數是 constant function；如果不是，代表這函數是 balanced function。

不管函數有幾個變量時，量子電腦都只需要計算 1 次，因此演算法複雜度為 $O(1)$，相比經典電腦，當變數越多時，量子電腦所謂的加速作用會越明顯

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/SJ5auEY1Jl.svg" alt="圖片內容" width="90%"/>
<br>
<p>藍色和橘色都是經典電腦，藍色是透過最笨的方式，橘色則是經第二種解法；灰色則為量子電腦。當函數的變數來到 5 個時，經典電腦最少也需要計算 17 次，而量子電腦僅需 1 次，大大減少計算所需時間
</p>
</div>

## 範例
回到前面提的例子：

\begin{split}
f(x_0,x_1)=x_0\oplus x_1
\end{split}

這函數有兩個變數，所以要用 3 個 qubits，DJ 演算法基本會長這樣：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/rkJxK4tJ1e.svg" alt="圖片內容" width="100%"/>
<br>
<p>後面還有測量動作，這邊沒有秀出來
</p>
</div>

中間的 $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$ 有一部分長這樣：

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/Bkf-KNKyJe.svg" alt="圖片內容" width="100%"/>
<br>
<p>
</p>
</div>

緊接著是第二項 $[(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，所以完整電路長這樣

<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/SkwMYNK1ke.svg" alt="圖片內容" width="100%"/>
<br>
<p>
</p>
</div>

簡單自己算一下，或是用 Qiskit composer 操作，這測量結果不是 $|00\rangle$，所以這函數是 balanced function。

## 演算法的應用
現在，給你點時間想想這演算法能應用在生活上什麼地方。

沒錯！沒有，不過這不代表這演算法沒有任何價值，事實上它在量子計算發展的初期提供一個很好的模型，展示量子電腦如何“加速”計算，比經典電腦更快。

這邊作者特別介紹，比 DJ 演算法更快的算法，只要看到多變數的 function，先猜 "balance function" 就對了，你會發現在多變數的情況下，要湊出 "constant function" 並不容易。