演算法解釋 2

本章節將繼續解釋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}$$

而後，我們再通過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{3}$$

內積的性質(同時也適用於量子)

$$\vec{x}\cdot\vec{y}=|\vec{x}||\vec{y}\|cos\theta$$

我們以下圖表是目前的量子態，$i_0$為搜尋目標， 可將其他量子態( $\sum{|x\rangle}-|i_0\rangle$)視為一個子群，正交於 $i_0$ :

由於 $|\psi\rangle$ 和 $|\psi_1\rangle$ 只在 $i_0$ 方向差了個負號，因此我們可以將 $|\psi\rangle$ 水平軸為基準映射出 $|\psi_1\rangle$，並算一下夾角(機率幅總和是 $1$ ) :

$$\begin{aligned} \langle\psi|\psi_1\rangle &=1\cdot1\cdot\cos\theta\\ &=1-\frac{2}{2^n}\tag{4} \end{aligned}$$

在前一節我們有提到，之後經過的diffusion Operator 是將 $|\psi_1\rangle$ 基於平均的翻轉，並且重新將 $i_0$ 機率幅翻為正的，所以我們假設 $|\psi_G\rangle$ 和| $\psi\rangle$ 的夾角為 ${\theta}^{′}$ ，並帶入(3)

$$\begin{aligned} \theta^′ &=\langle\psi|\psi_G\rangle\\ &=\langle\psi|(2|\psi\rangle\langle\psi|-I)|\psi_1\rangle\\ &=2\cdot1\cdot\langle\psi|\psi_1\rangle-\langle\psi|\psi_1\rangle\\ &=\langle\psi|\psi_1\rangle\\ &=\theta\tag{5} \end{aligned}$$

根據(5)，我們可以知道兩個角相等，但是 $|\psi\rangle$ 、 $|\psi_1\rangle$ 、 $|\psi_G\rangle$ 都是最原始的狀態，我們必須接著證明不論何時，Diffusion Operator 都是基於 $|\psi\rangle$ 的翻轉 :

在上圖中， $|\sigma\rangle$是初始狀態，經過 $U_f$ 後變成 $|\sigma_1\rangle$ ，再經過Diffusion Operator 後是 $G|\sigma\rangle$ ，首先化簡 $G|\sigma\rangle$ :

$$\begin{aligned} G|\sigma\rangle &=(2|\psi\rangle\langle\psi|-I)U_f(|\sigma\rangle)\\ &=2U_f\langle\psi|\sigma\rangle-|\sigma_1\rangle\\ &=2\cos{\alpha_2}|\psi\rangle-|\sigma_1\rangle\tag{6} \end{aligned}$$

接著計算夾角 $\theta$ :

$$\begin{aligned} \langle\sigma|G|\sigma\rangle &=\langle\sigma|(2\cos{\alpha_2}|\psi\rangle-|\sigma_1\rangle)\\ &=2\cos\alpha_2\langle\sigma|\psi\rangle-\langle\sigma|\sigma_1\rangle\\ &=2\cos\alpha_1 \cos\alpha_2-\cos(\alpha_1+\alpha_2)\\ &= \cos(\alpha_2-\alpha_1)\\ \tag{7} \end{aligned}$$

由此可知

$$\theta=\alpha_2-\alpha_1\tag{8}$$

也就是每次翻轉前後會差一個 $\theta$ ，也就是說地K次翻轉後，我們可以得到 $G|\sigma_k\rangle$ 的夾角為 :

$$\frac{\theta}{2}+\theta k\tag{9}$$

不停地經過翻轉後， $G|\sigma\rangle$ 會越來越高並且越來越接近 $i_0$ ，也就是說有更大的機率測得正確答案，然而，一但超過某個次數，越到第二象限之後，就會變小，所以我們希望能求得最接近 $|i_0\rangle$ 的操作次數。

首先是三角函數的性質

$$\arcsin{\theta}\approx\theta\tag{10}$$

一開始的 $\arcsin \theta = \frac{2}{\sqrt{2^n}}$ ，根據(10)，當n很大時

$$\theta = \frac{2}{\sqrt{2^n}}\tag{11}$$

經過k次之後

$$(2k+1)(\frac{\theta}{2})$$

而我們希望找到機率波的最接近 $i_0$ ， $i_0$ 與水平夾角是 $\frac{\pi}{2}$

$$(2k+1)(\frac{\theta}{2})=\frac{\pi}{2}\tag{12}$$

將 $\theta$ 帶入

$$(2k+1)(\frac{1}{\sqrt{2^n}})=\frac{\pi}{2}$$

簡化整理

$$k=\frac{\pi\sqrt{2^n}}{4}-\frac{1}{2}$$

因此時間複雜度為

$$O(\sqrt{2^n})=O(\sqrt{N})$$

和第一種解釋能得到相同的結果。