# Deutsch-Jozsa Algorithm（下）
這篇我們將用數學說明 DJ 演算法如何運作。在 Deutsch 演算法的介紹文章中，我們列舉各種情況並一步一步推導，然而，DJ 演算法就難以用這樣的方式推導，因為它將問題延伸到好幾個 qubits，我們必須使用稍微複雜的數學做說明。

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

一樣，我們將電路拆成四個部分，$|\psi_0\rangle$ 到 $|\psi_4\rangle$，逐一討論每個部分發生什麼事

## $|\psi_0\rangle$
很明顯地，就是

\begin{split}
|0\rangle^{\otimes n}|1\rangle
\end{split}

## $|\psi_1\rangle$

這邊我們拆成兩部分，分別是 $|0\rangle^{\otimes n}$ 經過 H gate 操作，與最後一個 qubits $|1\rangle$ 經過 H gate 操作，我們先從後者開始，比較簡單：

\begin{align} \tag{1}
H|1\rangle=\frac{1}{\sqrt 2}(|0\rangle-|1\rangle)
\end{align}

前面 $|0\rangle^{\otimes n}$ 經過 H gate 操作會變成：

\begin{align} \tag{2}
H|0\rangle^{\otimes n}=\frac{1}{\sqrt 2}(|0\rangle+|1\rangle) \otimes \frac{1}{\sqrt 2}(|0\rangle+|1\rangle) \otimes \frac{1}{\sqrt 2}(|0\rangle+|1\rangle) \otimes ....\otimes \frac{1}{\sqrt 2}(|0\rangle+|1\rangle)
\end{align}

可以把上式簡寫成：

\begin{align} \tag{3}
H|0\rangle^{\otimes n}=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle
\end{align}

可以試著將 $x$ 代入 0 與 1 進去，展開出來就是 (2) 式。將方程式 (3) 與 (2) 合在一起就是：

\begin{align}
|\psi_1\rangle=(\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle)\otimes \frac{1}{\sqrt 2}(|0\rangle-|1\rangle)
\end{align}

## $|\psi_2\rangle$

這邊會是這篇文章最複雜的地方

\begin{align}
|\psi_2\rangle&=U_f|\psi_1\rangle \\
&=U_f[\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle\otimes \frac{1}{\sqrt 2}(|0\rangle-|1\rangle)] \tag{4}\\
\end{align}

$U_f$ 只會作用在最後一個 qubit，其作用是 $y\oplus f(x)$，所以 (4) 式後面最後一項會變成：

\begin{align}
|\psi_2\rangle
&=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle\otimes \frac{1}{\sqrt 2}[|0\oplus f(x)\rangle-|1\oplus f(x)\rangle] \\
&=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle \otimes \frac{1}{\sqrt 2}[| f(x)\rangle-|1\oplus f(x)\rangle] \tag{5}
\end{align}

後面 $|0\oplus f(x)\rangle$ 變成 $| f(x)\rangle$ 就是因為... 0 加任何數字就是數字本身。現在我們看後面最後一項 $| f(x)\rangle-|1\oplus f(x)\rangle$，$f(x)$ 說到底要嘛是 0 就是 1，當 $f(x)=0$ 時：

\begin{align} \tag{6}
\frac{1}{\sqrt 2}[|f(x)\rangle-|1\oplus f(x)\rangle]&=\frac{1}{\sqrt 2}(|0\rangle-|1\oplus 0\rangle) \\
&=\frac{1}{\sqrt 2}(|0\rangle-|1\rangle)
\end{align}

如果 $f(x)=1$：

\begin{align} \tag{7}
\frac{1}{\sqrt 2}[|f(x)\rangle-|1\oplus f(x)\rangle]&=\frac{1}{\sqrt 2}(|1\rangle-|1\oplus 1\rangle) \\
&=\frac{1}{\sqrt 2}(1\rangle-|0\rangle)
\end{align}

將 (6) 式與 (7) 式合在一起就是：

\begin{align} \tag{8}
\frac{1}{\sqrt 2}(-1)^{f(x)}(|0\rangle-|1\rangle)
\end{align}

將 (8) 式代回 (5) 式：

\begin{align}
|\psi_2\rangle
&=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle \otimes \frac{1}{\sqrt 2}[| f(x)\rangle-|1\oplus f(x)\rangle] \\
&=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}|x\rangle \otimes \frac{1}{\sqrt 2}(-1)^{f(x)}(|0\rangle-|1\rangle) \\
&=\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt 2^n}(-1)^{f(x)}|x\rangle \otimes \frac{1}{\sqrt 2}(|0\rangle-|1\rangle) \tag{9}
\end{align}

## $|\psi_3\rangle$

在量子計算（上），我們提過一次對多個 qubits 做 H gate 操作，可以寫成：

\begin{align}
H^{\otimes n}&=
\frac{1}{\sqrt{2^n}} \sum_{u,v} (-1)^{u\cdot v}|v\rangle\langle u|
\end{align}

因此：

\begin{align}
H^{\otimes n}|u\rangle&=
\frac{1}{\sqrt{2^n}} \sum_{u,v} (-1)^{u\cdot v}|v\rangle\langle u|u\rangle \\
&=\frac{1}{\sqrt{2^n}}\sum_{v \in \{0,1\}} (-1)^{u\cdot v}|v\rangle \tag{10}
\end{align}

將 (10) 式套入 (9) 式：

\begin{align}
H^{\otimes n}(\sum_{x\in \{0,1\}^n} \frac{1}{\sqrt{2^n}}(-1)^{f(x)}|x\rangle)&=\frac{1}{\sqrt{2^n}}\frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n}(-1)^{f(x)} \sum_{v\in \{0,1\}^n} (-1)^{x\cdot v}|v\rangle \\
&=\frac{1}{2^n} \sum_{x\in \{0,1\}^n}(-1)^{f(x)} \sum_{v\in \{0,1\}^n} (-1)^{x\cdot v}|v\rangle \\
&=\frac{1}{2^n} \sum_x \sum_v (-1)^{f(x)}(-1)^{x\cdot v}|v\rangle \tag{11}
\end{align}

## $|\psi_4\rangle$

如果今天要判斷的函數 $f(x)$ 是 constant function：

\begin{align}
(11) = \frac{1}{2^n}(-1)^{f(x)}\sum_x \sum_v (-1)^{x\cdot v}|v\rangle
\end{align}

先來仔細看這一項 $\sum_x \sum_v (-1)^{x\cdot v}|v\rangle$，$x$ 和 $v$ 要嘛是 0 要嘛就是 1，當 $v$ 是 0 時：

\begin{align}
\sum_{x\in \{0,1\}}^n (-1)^{x\cdot 0}|0\rangle=\sum_{x\in \{0,1\}}^n |0\rangle=2^n|0\rangle^{\otimes n}
\end{align}

當 $v$ 是 1 時：

\begin{align}
\sum_{x\in \{0,1\}}^n (-1)^{x\cdot 1}|1\rangle&=\sum_{x\in 0}^n (-1)^{0\cdot 1}|1\rangle+\sum_{x\in 1}^n (-1)^{1\cdot 1}|1\rangle \\
&=\sum_{x\in 0}^n (-1)^0|1\rangle+\sum_{x\in 1}^n (-1)^1|1\rangle \\
&=\sum_{x\in 0}^n 1|1\rangle+\sum_{x\in 1}^n -1|1\rangle \\
&=0
\end{align}

合在一起就是：

\begin{align}
(11) &= \frac{1}{2^n}(-1)^{f(x)}\sum_x \sum_v (-1)^{x\cdot v}|v\rangle \\
&=\frac{1}{2^n} (-1)^{f(x)} 2^n|0\rangle^{\otimes n} \\
&=(-1)^{f(x)}|0\rangle^{\otimes n}
\end{align}

不管今天這個 constant function $f(x)$ 永遠輸出 0 還是 1，上式會變成：

\begin{align} \tag{12}
&\text{if }f(x)=0, (-1)^{f(x)}|0\rangle^{\otimes n}=|0\rangle^{\otimes n}\\
&\text{if }f(x)=1, (-1)^{f(x)}|0\rangle^{\otimes n}=-|0\rangle^{\otimes n} \tag{13}
\end{align}

以上兩種情況 (12) 與 (13) 的測量結果都會是 $|0\rangle^{\otimes n}$，的確當測量結果都是 0 時，代表這函數是 constant function。

反之，只要不是這結果，都是 balance function。