經典 vs Grover

本章節只會介紹演算法的結構與時間複雜度，下個章節將會加以解釋

1. 經典算法

在一個沒有任何資料結構排序過的資料庫中，如果要尋找一筆特定資料，那我們只能一筆一筆地尋找直到找到為止，平均需要 $\frac{N}{2}$ ，最糟需要 $N$，因此時間複雜度為 $O(N)$ 。

2. 量子算法

Grover's algorithm 的時間複雜度與結構

Grover's algorithm 的時間複雜度為 $O(\sqrt{N})$ ，以下為其結構 :

Grover's algorithm structure

每個 Grover iteration ( $G$ )可視為一個步驟，其結構如下 :

Oracle $U_f$是個phase Oracle，輸入一個函數 $f : \left\{0,\cdots,N-1\right\} \rightarrow \left\{0,1\right\}$ ，輸出如下 :

達到以下效果

$$|i\rangle\rightarrow(-1)^{f(i)}|i\rangle$$

Grover's algorithm 其實很簡單，就是重複做 Grover iteration(也就是 $U_f$ 以及 $2|\psi\rangle\langle\psi|\ -\ I$ ) $O(\sqrt{N})$ 次後觀察，即可得到答案。