演算法解釋

本章節將詳細解釋grover search

再看一次圖 :

首先，經過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^*$ 的機率幅變為負號

也就是將一開始 :

變成 :

由於一開始的機率幅都是 $\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^*$ 的機率幅依據平均再翻轉一次，並且其他量子態同時變小

從 :

成 :

至於這個步驟為何能做到，讓我們來思考一下，首先，我們要確保每次做這個步驟都有相同的效果，所以我們假設通過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，讓大家能更深入了解。