演算法解釋 2

本章節將繼續解釋grover search

首先我們先來複習一下上個章節所說的東西

首先,經過headamard transform 後 :

ψ=12nx{0,1}nx(1)|\psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\left\{0,1\right\}^n}|x\rangle\tag{1}

接下來經過Oracle UfU_f :

Uf(ψ)ψ1(2)U_f(|\psi\rangle)\rightarrow|\psi_1\rangle\tag{2}

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

ψG=(2ψψI)ψ1=2ψψψ1ψ1=2(ψ)(122n)(ψ22nx)=(2n+122n)2n)ψ22nx(3)\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}

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

xy=xycosθ\vec{x}\cdot\vec{y}=|\vec{x}||\vec{y}\|cos\theta

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

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

ψψ1=11cosθ=122n(4)\begin{aligned} \langle\psi|\psi_1\rangle &=1\cdot1\cdot\cos\theta\\ &=1-\frac{2}{2^n}\tag{4} \end{aligned}

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

θ=ψψG=ψ(2ψψI)ψ1=21ψψ1ψψ1=ψψ1=θ(5)\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ψ1|\psi_1\rangleψG|\psi_G\rangle 都是最原始的狀態,我們必須接著證明不論何時,Diffusion Operator 都是基於 ψ|\psi\rangle 的翻轉 :

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

Gσ=(2ψψI)Uf(σ)=2Ufψσσ1=2cosα2ψσ1(6)\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 :

σGσ=σ(2cosα2ψσ1)=2cosα2σψσσ1=2cosα1cosα2cos(α1+α2)=cos(α2α1)(7)\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}

由此可知

θ=α2α1(8)\theta=\alpha_2-\alpha_1\tag{8}

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

θ2+θk(9)\frac{\theta}{2}+\theta k\tag{9}

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

首先是三角函數的性質

arcsinθθ(10)\arcsin{\theta}\approx\theta\tag{10}

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

θ=22n(11) \theta = \frac{2}{\sqrt{2^n}}\tag{11}

經過k次之後

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

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

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

θ\theta 帶入

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

簡化整理

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

因此時間複雜度為

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

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

Last updated

Was this helpful?