# 經典 vs Grover

### 1.  經典算法

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

### 2.  量子算法

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

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

![Grover's algorithm structure](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LpNoXcuVJ5wF21SbJuI%2F-LpNxpekCqi35nBvSBc5%2Fimage.png?alt=media\&token=dda14b1b-fe48-4f1b-bf0a-8092f4495ea0)

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

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LpNoXcuVJ5wF21SbJuI%2F-LpNz7goDGppsipoq_d1%2Fimage.png?alt=media\&token=09cf2ff7-b910-4d7a-8a94-46c62a84fdc3)

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