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

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

一樣，我們將電路拆成四個部分，$|\psi_0\rangle$ 到 $|\psi_3\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} ## $|\psi_5\rangle$ 以上兩種情況 (12) 與 (13) 的測量結果都會是 $|0\rangle^{\otimes n}$，的確當測量結果都是 0 時，代表這函數是 constant function。反之，只要不是這結果，都是 balance function。