> For the complete documentation index, see [llms.txt](https://chiwei955201314.gitbook.io/quantum/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chiwei955201314.gitbook.io/quantum/untitled/jing-dian-vs-liang-zi.md).

# 經典 vs Grover

### 1.  經典算法

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

### 2.  量子算法

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

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

![Grover's algorithm structure](/files/-LpNxpekCqi35nBvSBc5)

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

![](/files/-LpNz7goDGppsipoq_d1)

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