# Deutsch Algorithm
###### tags:`quantum computing`
## Boolean Functions
- $f:\{0,1\} \rightarrow \{0, 1\}$
- $f_0(x)=0, f_1(x) = 1, f_2(x)=x, f_3(x)=\bar{x}$
- $f_0, f_1$ 是 constant function
- $f_2, f_3$ 是 balance function
### n-input and single output
- 以布林表示式表達 $f(x_1,x_2,\dots)$
- e.g. $f(x_1,x_2) = x_1+\bar{x_2}$
- $n\geq 2$ 時，function 不是 1-1 且 onto
- $f:\{0,1\}^n\rightarrow\{0,1\}^m$
<div style="text-align: center;">
<img src="https://hackmd.io/_uploads/B1vYrBbMgl.png" alt="圖片">
</div>
- 可以總共有 $\overbrace{2^m \times 2^m \times \dots \times 2^m}^{2^n}$ $= (2^m)^{2^n}$ 的 boolean function。
### 將不可逆的 boolean function 轉為可逆的 unitary operator
- 因為量子閘必須是可逆（unitary）的
- 利用額外的 qubit 確保可逆性
- 給定 $f:\{0,1\}^n\rightarrow\{0,1\}^1$
- 可逆化(unitary)步驟如下
$$
\begin{aligned}
U_f(|x\rangle_n|y\rangle) = U_f(|y,x\rangle_{n+1}) = U_f(|y\rangle\otimes|x\rangle_n) = |y\oplus f(x)\rangle\otimes|x\rangle
\end{aligned}
$$
- 這樣一來 $U_f$ 的定義域(domain)和對應域(codomain)為
$$
C^{2^{n+1}}=\big[|0\rangle_{n+1}, |1\rangle_{n+1}, \dots, |2^n\rangle_{n+1}\big]
$$
- 以上是以十進制表示
- 例如
- $|0\rangle\otimes|0\rangle = |0\rangle_{2}$
- $|1\rangle\otimes|0\rangle = |2\rangle_{2}$
- $U_f$ 電路
- CNOT gate 的邏輯 : $\text{CNOT}(∣\text{c}\rangle\space\otimes∣\text{t}\rangle)=∣c\rangle⊗∣t\oplus c\rangle$
- $a\oplus a = 0$
- $a\oplus 0 = a$
- proof : $U_f$ is reversible
$$
\begin{aligned}
U_f(U_f(|y,x\rangle_{n+1})) &= U_f(|y\space\oplus f(x),x\rangle)\\
&= |(y \oplus f(x))\oplus f(x), x\rangle_{n+1}\\
&= |y\space\oplus (f(x)\oplus f(x)), x\rangle_{n+1}\\
&= |y,x\rangle_{n+1}
\end{aligned}
$$
### $U_{f_{OR}}$
- $f_{OR}$ 的 truth table
$$
\begin{array}{|c|c|}
\hline
\text{$x_1$} &\text{$x_1$} & \text{$f_{OR}(x_1,x_2)$}\\
\hline
0 &0 & 0 \\
\hline
0& 1& 1\\
\hline
1& 0& 1\\
\hline
1& 1& 1\\
\hline
\end{array}
$$
- $U_{f_{OR}}$ 的 truth table
$$
\begin{array}{|c|c|}
\hline
\text{input($|y\rangle\otimes|x\rangle_{2}$)}&\text{$|y\oplus f_{OR}(x)\rangle\otimes|x\rangle_2$}\\
\hline
|0\rangle_3& |0\rangle_3\\
\hline
|1\rangle_3& |5\rangle_3\\
\hline
|2\rangle_3& |6\rangle_3\\
\hline
|3\rangle_3& |7\rangle_3\\
\hline
|4\rangle_3& |4\rangle_3\\
\hline
|5\rangle_3& |1\rangle_3\\
\hline
|6\rangle_3& |2\rangle_3\\
\hline
|7\rangle_3& |3\rangle_3\\
\hline
\end{array}
$$
- $\beta = \{\text{input}(|y\rangle\otimes|x\rangle_{2})\}\xrightarrow{[T]^{\beta}_{\beta'}} \beta'=\{|y\oplus f_{OR}(x)\rangle\otimes|x\rangle_2\}$，這個 transformation matrix 就是 $U_{f_{OR}}$
$$
\begin{bmatrix}
\overset{|000\rangle}{1} & \overset{|001\rangle}{0}& \overset{|010\rangle}{0}& \overset{|011\rangle}{0}& \overset{|100\rangle}{0}& \overset{|101\rangle}{0}& \overset{|110\rangle}{0}& \overset{|111\rangle}{0}\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0
\end{bmatrix}
$$
- MSB : $|x_1,x_0,y\rangle$
- LSB : $|y,x_1,x_0\rangle$
- $U_{f_{OR}}$ 的 quantum ciruit
## Deutsch演算法的由來及概念
- 1985年，Prof. Deutsch 提出一種量子演算法，展現出量子計算的潛在能力，
傳統電腦的計算模型將無法比擬。
- 該演算法的實用價值雖有限，但它引入了量子平行和量子干涉的概念，為未來
量子程式立下一個典範。
- ==**Deutsch algorithm 的目的是判斷f是否為平衡函數**==
- 另外，於1992年提出的改進的Deutsch–Jozsa algorithm，用於判斷 $f:\{0,1\} \rightarrow \{0, 1\}$ 是否為平衡函數？
### 傳統電腦的演算法
- time complexity : $O(2^n)$ $\rightarrow$ Deutsch 可以 $O(1)$
\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}
## Deustch演算法
### state 1:
對 input 做基底變換
$\beta_1 =\{|0\rangle, |1\rangle\}\rightarrow \beta_2=\{|+\rangle, |-\rangle\}$
$$
\begin{aligned}
|\psi_1\rangle : H|1\rangle\otimes H|0\rangle = |-\rangle\otimes|+\rangle
\end{aligned}
$$
- 經過 uniform gate，$|+\rangle$ 會對 $|-\rangle$ 產生 phase kickback : $e^{i0}|-\rangle$
- 經過 uniform gate，$|-\rangle$ 會對 $|+\rangle$ 產生 phase kickback : $e^{i\pi}|-\rangle$
### state 2
$$
\begin{aligned}
|\psi_2\rangle &= U_f(|-\rangle\otimes(\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle))\\
&=U_f(\frac{1}{\sqrt{2}}|-\rangle\otimes|0\rangle+\frac{1}{\sqrt{2}}|-\rangle\otimes|1\rangle)\\
&= \frac{1}{\sqrt{2}}\overbrace{U_f(|-\rangle\otimes|0\rangle)}^{\text{case 1}}+\frac{1}{\sqrt{2}}\underbrace{U_f(|-\rangle\otimes|1\rangle)}_{\text{case 2}}
\end{aligned}
$$
- case 1
$$
\begin{aligned}
U_f(|-\rangle\otimes|0\rangle &= U_f((\frac{1}{\sqrt{2}}|0\rangle-\frac{1}{\sqrt{2}}|1\rangle)\otimes|0\rangle)\\
&= \frac{1}{\sqrt{2}}U_f|00\rangle-\frac{1}{\sqrt{2}}U_f|10\rangle\\
&= \frac{1}{\sqrt{2}}|0\oplus f(0)\rangle\otimes|0\rangle - \frac{1}{\sqrt{2}}|1\oplus f(0)\rangle\otimes|0\rangle\\
\end{aligned}
$$
$$
\begin{cases}
\frac{1}{\sqrt{2}}|0\rangle\otimes|0\rangle - \frac{1}{\sqrt{2}}|1\rangle\otimes|0\rangle = |-\rangle\otimes|0\rangle, \quad &\text{if f(0) = 0}\\
\frac{1}{\sqrt{2}}|1\rangle\otimes|0\rangle-\frac{1}{\sqrt{2}}|0\rangle\otimes|0\rangle = (-1)|-\rangle\otimes|0\rangle, \quad &\text{if f(0) = 1}
\end{cases}
$$
$$
\begin{aligned}
\text{case1} = (-1)^{f(0)}|-\rangle\otimes|0\rangle
\end{aligned}
$$
- case 2
$$
\begin{aligned}
U_f(|-\rangle\otimes|1\rangle &= U_f((\frac{1}{\sqrt{2}}|0\rangle-\frac{1}{\sqrt{2}}|1\rangle)\otimes|1\rangle)\\
&= \frac{1}{\sqrt{2}}U_f|01\rangle-\frac{1}{\sqrt{2}}U_f|11\rangle\\
&= \frac{1}{\sqrt{2}}|0\oplus f(1)\rangle\otimes|1\rangle - \frac{1}{\sqrt{2}}|1\oplus f(1)\rangle\otimes|1\rangle\\
\end{aligned}
$$
$$
\begin{cases}
\frac{1}{\sqrt{2}}|0\rangle\otimes|1\rangle - \frac{1}{\sqrt{2}}|1\rangle\otimes|1\rangle = |-\rangle\otimes|1\rangle, \quad &\text{if f(1) = 0}\\
\frac{1}{\sqrt{2}}|1\rangle\otimes|1\rangle-\frac{1}{\sqrt{2}}|0\rangle\otimes|1\rangle = (-1)|-\rangle\otimes|1\rangle, \quad &\text{if f(1) = 1}
\end{cases}
$$
$$
\begin{aligned}
\text{case2} = (-1)^{f(1)}|-\rangle\otimes|1\rangle
\end{aligned}
$$
- 帶回原式
$$
\begin{aligned}
|\psi_2\rangle &= (-1)^{f(0)}\frac{1}{\sqrt{2}}|-\rangle\otimes|0\rangle + (-1)^{f(1)}\frac{1}{\sqrt{2}}|-\rangle\otimes|1\rangle\\
&= |-\rangle\otimes\frac{1}{\sqrt{2}}\bigg[(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigg]
\end{aligned}
$$
### state 3
$$
\begin{aligned}
|\psi_3\rangle &= (I\otimes H)( |-\rangle\otimes\frac{1}{\sqrt{2}}\bigg[(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigg])\\
&=I|-\rangle\otimes \frac{1}{\sqrt{2}}((-1)^{f(0)}H|0\rangle + (-1)^{f(1)}H|1\rangle)\\
\end{aligned}
$$
$$
\begin{aligned}
|\psi_3\rangle &=
\begin{cases}
|-\rangle\otimes H|+\rangle, &\text{if f(0) = 0, f(1) = 0}\\
|-\rangle\otimes H(-|+\rangle), &\text{if f(0) = 1, f(1) = 1}\\
|-\rangle\otimes H|-\rangle, &\text{if f(0) = 0, f(1) = 1}\\
|-\rangle\otimes H(-|-\rangle), &\text{if f(0) = 1, f(1) = 0}\\
\end{cases}\\
&=
\begin{cases}
|-\rangle\otimes H|0\rangle, &\text{if f(0) = 0, f(1) = 0}\\
|-\rangle\otimes H(-|0\rangle), &\text{if f(0) = 1, f(1) = 1}\\
|-\rangle\otimes H|1\rangle, &\text{if f(0) = 0, f(1) = 1}\\
|-\rangle\otimes H(-|1\rangle), &\text{if f(0) = 1, f(1) = 0}\\
\end{cases}
\end{aligned}
$$
### conclusion
$$
\begin{aligned}
&|-\rangle\otimes H|0\rangle, \text{if f(0) = 0, f(1) = 0} \Rightarrow (\text{write out})|0\rangle \rightarrow 0 (\text{constant})\\
&|-\rangle\otimes H(-|0\rangle), \text{if f(0) = 1, f(1) = 1} \Rightarrow (\text{write out})(-|0\rangle) \rightarrow 0 (\text{constant})\\
&|-\rangle\otimes H|1\rangle, \text{if f(0) = 0, f(1) = 1} \Rightarrow (\text{write out})|1\rangle \rightarrow 1 (\text{balanced})\\
&|-\rangle\otimes H(-|1\rangle), \text{if f(0) = 1, f(1) = 0} \Rightarrow (\text{write out})(-|1\rangle) \rightarrow 1 (\text{balanced})\\
\end{aligned}
$$
## Reference
- [Deutsch Algorithm（上）](https://hackmd.io/lD8cYHjPSWSqWnuG1gapqg?view)
- [Deutsch 演算法（下）](https://hackmd.io/2O5JzSUsQl69MfFSXQU6Ag#Deutsch-%E6%BC%94%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%8B%EF%BC%89)
- Prof. Pao-Ta Yu. 2025. 量子電腦程式設計概論. ch05 Deutsch–Jozsa Algorithm,中正大學, Chiayi, Taiwan。
Sign in with Wallet
Connect another wallet