經典 vs Grover

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

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

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

達到以下效果

Last updated 5 years ago

Was this helpful?

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

每個 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})$ 次後觀察，即可得到答案。

每個 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})$ 次後觀察，即可得到答案。