經典 vs Deutsh-Jozsa

本小節將比較經典算法與Deutsh-Jozsa算法下的差異

1. 經典算法

在經典情況下，當你必須計算 $f(0)\oplus f(1)$ ，ㄧ定必需query兩次並且相加才能找出答案

2. Deutsh-Jozsa

首先我們必須先準備一個qbit，並初始化在 $|0\rangle$ ，並經過hadamard gate變成 $\frac{|0\rangle+|1\rangle}{\sqrt{2}}$ ，接著我們query一次phase oracle，得到下者

$$|\psi'\rangle=\frac{(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle}{\sqrt{2}}$$

接著我們思考 $f(0)$ 和 $f(1)$ 的關係

$$f(0)\oplus f(1)= \begin{cases} \ 0,\ \text{if}\ f(0)=f(1)\\ \ 1,\ \text{if} \ f(0)\neq f(1) \end{cases}$$

而根據(1)，我們又可以得到下者

$$|\psi'\rangle= \begin{cases} (\pm1)\cdot\frac{|0\rangle+|1\rangle}{\sqrt{2}}, \text{if}\ f(0)=f(1) \\ (\pm 1)\cdot \frac{|0\rangle-|1\rangle}{\sqrt{2}}, \text{if}\ f(0)\neq f(1) \end{cases}$$

這時，我們只要再經過一次hadamard gate，並且觀測 $|\psi'\rangle$ ，就能一路推回去了，以下我舉個例子：

$$\begin{aligned} |\psi'\rangle = |0\rangle &\rightarrow f(0) = f(1)\\ &\rightarrow f(0)+f(1)=0 \end{aligned}$$

而以上算法相較於經典算法只需要一次quey就能得出答案。