# 演算法解釋

再看一次圖 :

![](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)

首先，經過headamard transform 後 :

$$
|\psi\rangle=\frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}|x\rangle\tag{1}
$$

接下來經過Oracle $$U\_f$$ :

$$
U\_f(|\psi\rangle)\rightarrow|\psi\_1\rangle\tag{2}
$$

而在前面，我們已知 $$U\_f$$ 的功能如下:

$$
|\psi\_1\rangle\rightarrow\frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}(-1)^{f(x)}|x\rangle\tag{3}
$$

 假設我們目標搜尋 $$x^*$$ ，我們可以將query oracle步驟想像成將目標 $$x^*$$ 的機率幅變為負號

也就是將一開始 :

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-Lpt_Q9NvDUyJ7Jl7L_c%2F-LptaHcHXGOPHvg-3GvF%2Fimage.png?alt=media\&token=4887d6a8-8817-405d-95ca-af952e8c19ce)

變成 :

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-Lpt_Q9NvDUyJ7Jl7L_c%2F-LptahgHh5PUyckuS3EP%2Fimage.png?alt=media\&token=a894861f-9e4d-4ed5-b28a-3742bcd215e7)

由於一開始的機率幅都是 $$\frac{1}{\sqrt{2^n}}$$ ，因此我們可以由(1)、(2)推倒出以下一些關係備用 :

$$
|\psi\_1\rangle = |\psi\rangle-\frac{2}{\sqrt{2^n}}|x^\*\rangle\tag{4}
$$

$$
\langle\psi|x^\*\rangle = \frac{1}{\sqrt{2^n}}\tag{5}
$$

而後，我們再通過Grover Diffusion Operator，也就是 $$2|\psi\rangle\langle \psi|-I$$ ，可以得到 :

$$
\begin{aligned}
|\psi\_G\rangle
&=(2|\psi\rangle\langle\psi|-I)|\psi\_1\rangle\\
&=2|\psi\rangle\langle\psi|\psi\_1\rangle-|\psi\_1\rangle\\
&=2(|\psi\rangle)(1-\frac{2}{2^n})-(|\psi\rangle-\frac{2}{\sqrt{2^n}}|x^*\rangle)\\
&=(\frac{2^{n+1}-2-2^{n})}{2^n})|\psi\rangle-\frac{2}{\sqrt{2^n}}|x^*\rangle
\end{aligned}\tag{6}
$$

而這個步驟的功能，是讓 $$x^\*$$ 的機率幅依據平均再翻轉一次，並且其他量子態同時變小

從 :

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LptkF4EofLEvAQ_qWep%2F-LptkJILw80scK6c5Lco%2Fimage.png?alt=media\&token=5caf7eb9-9709-4d50-922d-3ab3eed05108)

成 :

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LptkF4EofLEvAQ_qWep%2F-LptkOmwb8fHqdAUGOTy%2Fimage.png?alt=media\&token=7e7b12eb-1e90-423f-b551-5486d13e0348)

至於這個步驟為何能做到，讓我們來思考一下，首先，我們要確保每次做這個步驟都有相同的效果，所以我們假設通過Grover Diffusion Operator的量子態是 $$|\psi\_n\rangle$$ ，並且我們已 $$\alpha\_i$$ 代表 $$|i\rangle$$ 的機率幅，此時機率幅的平均是 :

$$
\mu =\frac{\sum\_{x\in\left{0,1\right}^n}\alpha\_i}{\sqrt{2^n}}\tag{7}
$$

讓我們將 $$|\psi\_n\rangle$$ 通過 Diffusion Operator，得到以下 :

$$
\begin{aligned}
(2|\psi\rangle\langle\psi|-I)|\psi\_n\rangle
&=2|\psi\rangle\langle\psi|\psi\_n\rangle-|\psi\_n\rangle\\
&=2(\sum\_{x\in\left{0,1\right}^n}{\alpha\_x})|\psi\rangle - |\psi\_n\rangle\\
&=2\mu\sqrt{2^n}|\psi\rangle-|\psi\_n\rangle\\
&=2\mu(\sqrt{2^n})(\frac{1}{\sqrt{2^n}}){\sum\_{x\in\left{0,1\right}^n}|x\rangle-\sum\_{x\in\left{0,1\right}^n}{\alpha\_x}|x\rangle}\\
&=\sum\_{x\in\left{0,1\right}^n}(2\mu-\alpha\_x)|x\rangle
\tag{8}
\end{aligned}
$$

由此可知，Diffusion Operator 是基於mean的翻轉，目標 $$x^\*$$ 的機率幅會被越翻越高，也因此觀測時會有更大機率觀測正確，以下是簡單的時間複雜度證明 :

我們預期觀測到正確答案的機率超過  

$$
\frac{1}{2}
$$

也就是說，目標 $$x^\*$$ 的機率幅為

$$
\frac{1}{\sqrt{2}}
$$

其他量子態機率幅為(平\[ 分配剩下的 $$\frac{1}{2}$$ )

$$
\frac{1}{\sqrt{2^{n+1}}}
$$

由(6)我們可以看出來，每次機率幅增加的幅度會減少，所以如果觀測機率已經到達 $$\frac{1}{2}$$ ，並且還再經過一次Diffusion Operator，會增加多少振福  ?

先算一下此時的機率幅平均( $$N=2^n$$ )

因為我們最終是以big-O來衡量，因此可以忽略一些 $$-1$$ 這類的操作，因為並不影響複雜度) :

$$
\begin{aligned}
\mu
&=\frac{\frac{1}{\sqrt{2}}+N(\frac{1}{\sqrt{N}})}{\sqrt{N}}\\
&=\frac{1}{\sqrt{2N}}\tag{9}
\end{aligned}
$$

此時，增加平率為

$$
\sqrt{\frac{2}{N}}\tag{10}
$$

按照以上所述，我們知道頻率增加的量會越來越小，而(10)是到目前為止最小的增加量，而距離我們就取遠一點，取完整的 $$\frac{1}{\sqrt{2}}$$ ，也就是說，用最短的距離走最遠的路，得到以下 :

$$
\frac{\frac{1}{\sqrt{2}}}{\sqrt{\frac{2}{N}}}=\sqrt{N}
$$

由此說明，grover search 的時間複雜度為

$$
O(\sqrt{N})
$$

相較於經典算法，是一種次方級的加速。

再下一小節，我們將會以另外一種方式講解grover search，讓大家能更深入了解。