06 - Grover 演算法 (Grover's Algorithm) [Unstructed Search]

簡介

Grover Algorithm 是量子電腦的搜尋演算法,他厲害的地方在於不需要排列就可達到O(n)O(\sqrt{n})
普通電腦的搜尋必須透過一個一個敲進去檢查
而這個演算法是透過一次觀察所有的狀況:透過黑箱,找到正確的目標,把其被測量到的震幅加大。而非目標者,震幅減小。
它也更近一步地展示了量子電腦如何戰勝普通電腦
這邊先快速帶過整個流程,隨後再來逐一解釋

演算法

  1. 將足夠的 Qubit 變成疊加態 (Superposition)
  2. 重複以下步驟,π42n\frac{\pi}{4}\sqrt{2^n} 次 — [Grover iteration]
    1. 放入黑箱 (Blackbox) — [Oracle Function]
    2. 放大震幅 (Amplitude Amplification) — [Diffusion transform]
  3. 測量

1 疊加態 (Superposition)

從現在開始我們用 3 顆 Qubits 來做解釋

符號 03|0\rangle^{\otimes 3} 就是有 330|0\rangle 的 Qubit,

他們的疊加態可以寫成:

ψ=H303=123x=0231x=000+....+1118|\psi\rangle = H^{\otimes 3}|0\rangle^{\otimes 3}= \frac{1}{\sqrt{2^3}}\sum_{x=0}^{2^3-1}|x\rangle = \frac{|000\rangle + .... + |111\rangle}{\sqrt{8}}

2-1 神諭 (Oracle)

假設有一個 Gate,以下簡稱 OO,他知道 f(x)f(x) 是什麼,然後如果正確 (1) 則翻轉 Qubit ,錯了 (0) 就沒事,就如同 Deutsch Algorithm 的 Blackbox,現在 xx 依然是疊加態,yy 換成 Oracle bit :

xyxyf(x)=(1)f(x)x|x\rangle|y\rangle\rightarrow|x\rangle|y\oplus f(x)\rangle= (-1)^{f(x)}|x\rangle

他可以幹嘛呢,假設我們要找的是 3?

Oracle\downarrow Oracle

因此,透過 OO-gategate,我們的 x|x\rangle 現在被翻了一個 3

這個 Oracle 必須自己設計 : y = F(x)

和電子電腦一樣,需要自己針對 (一個量子演算法 F,和輸入 y) 做出一個量子電路,來進行 Oracle

尚未有 general 的 Oracle 可以改 function 自動生成電路QQ …

2-2 擴散 (Diffusion)

曠散在做的事情就是把震幅放大,怎麼放大呢?

這個步驟又叫做 Diffusion transform,可以再當做另一個 Gate 以下簡稱 TT

T=2ψψIT = 2 |\psi\rangle\langle\psi| - I

以下證明 TxT|x\rangle 可以增幅,把剛剛的 xx 拿來繼續:

[2ψψI]x[2 |\psi\rangle\langle\psi| - I] |x\rangle

=[2ψψI][ψ222011]= [2 |\psi\rangle\langle\psi| - I] [|\psi\rangle - \frac{2}{2\sqrt{2}}|011\rangle]

=2ψψψψ22ψψ011+222011= 2 |\psi\rangle\langle\psi|\psi\rangle - |\psi\rangle -\frac{2}{\sqrt{2}}\psi\rangle\langle\psi|011\rangle + \frac{2}{2\sqrt{2}}|011\rangle

=2ψ(1)ψ22ψ122+222011= 2 |\psi\rangle(1) - |\psi\rangle -\frac{2}{\sqrt{2}}\psi\rangle\frac{1}{2\sqrt{2}} + \frac{2}{2\sqrt{2}}|011\rangle

=12ψ+12011= \frac{1}{2} |\psi\rangle + \frac{1}{\sqrt{2}}|011\rangle

=142x=07x+12011= \frac{1}{4\sqrt{2}}\sum_{x=0}^{7}|x\rangle + \frac{1}{\sqrt{2}}|011\rangle

=142x=0,x37x+142011+12011= \frac{1}{4\sqrt{2}}\sum_{x=0,x\neq3}^{7}|x\rangle +\frac{1}{4\sqrt{2}}|011\rangle + \frac{1}{\sqrt{2}}|011\rangle

=142x=0,x37x+542011= \frac{1}{4\sqrt{2}}\sum_{x=0,x\neq3}^{7}|x\rangle +\frac{5}{4\sqrt{2}}|011\rangle

看看這個結果A_A+

那這個奇怪的 Gate 要怎麼做??

其實沒很難,讓我們回到一開始來,ψ|\psi\rangle為其疊加態):

T=[2ψψI]T = [2 |\psi\rangle\langle\psi| - I]

由於 HH-gategate 是 Hermitian 矩陣,有一些特性:

aTb=Tab,with(T=T),T×T=I\langle a|Tb\rangle = \langle T^{\dagger}a|b\rangle , with (T=T^{\dagger}) , T\times T^{\dagger} = I

所以:

T=2ψψI=2H00HH2T = 2 |\psi\rangle\langle\psi| - I =2 H|0\rangle\langle0| H - H^2

=H[200I]H= H[2 |0\rangle\langle0| - I]H

整理一下裡面(暫定DD)會發現它是一個類似普通電腦 OR gate 的東西,如果不是 0,全部翻成 -1

D=200I=2[100....0000....000......0..........0..........0000000]2n×2nI=1×[100....0010....0001....0..........0........10000001]2n×2nD = 2 |0\rangle\langle0| - I = 2\begin{bmatrix} 1 & 0 & 0 & .. & .. & 0 \\ 0 & 0 & 0 & .. & .. & 0 \\ 0 & 0 & ..& .. & .. & 0 \\ .. & .. & .. & ..& ..& 0 \\ .. & .. & .. & ..& ..& 0 \\ 0 & 0 & 0 & 0 & 0 &0 \end{bmatrix}_{2^n\times2^n} - I = -1 \times \begin{bmatrix} -1 & 0 & 0 & .. & .. & 0 \\ 0 & 1 & 0 & .. & .. & 0 \\ 0 & 0 & 1& .. & .. & 0 \\ .. & .. & .. & ..& ..& 0 \\ .. & .. & .. & ..& 1& 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}_{2^n\times2^n}

[200I]x{=x,if x=00...00=x,if x=others[2 |0\rangle\langle0| - I]|x\rangle \Rightarrow \begin{cases}=|x\rangle, \text{if x=00...00}\\=-|x\rangle, \text{if x=others}\end{cases}

如果透過 XX-GateGate 把 0,1 對調之後,可以由下面兩種電路實作 :

CZ=HCNOTH=[100....0010....0001....0..........0........10000001]2n×2nCZ = H\otimes CNOT \otimes H = \begin{bmatrix} 1 & 0 & 0 & .. & .. & 0 \\ 0 & 1 & 0 & .. & .. & 0 \\ 0 & 0 & 1& .. & .. & 0 \\ .. & .. & .. & ..& ..& 0 \\ .. & .. & .. & ..& 1 & 0 \\ 0 & 0 & 0 & 0 & 0 &-1 \end{bmatrix}_{2^n\times2^n}

所以 D=Xn(Cn1Z)Xn-D = X^{\otimes n} \cdot (C^{n-1}Z) \cdot X^{\otimes n}

結論: T=HnXn(Cn1Z)XnHnT = - H^{\otimes n} \cdot X^{\otimes n} \cdot (C^{n-1}Z) \cdot X^{\otimes n} \cdot H^{\otimes n}
(因為測量結果,出現的機率為其平方,負號對結果沒什麼影響。)

2 Grover iteration

Grover iteration :重複以上 G 和 O Gate

這個循環要做 π42n\frac{\pi}{4}\sqrt{2^n} 次,nn 是放入的 Qubits 數 (n=log2N)(n = \log_2N)

π42n\frac{\pi}{4}\sqrt{2^n} ?? 哪來的 ??

假設一次的迭代 GψG|\psi\rangle 定做 G1G^{1}

Gr=(2r+1)θ2G^r = (2r+1)\frac{\theta}{2}

Gr=cosGrψ+sinGrtarget|G^r\rangle = \cos{G^r}|\psi'\rangle + \sin{G^r}|target\rangle(ψ(|\psi'\rangleψ|\psi\rangle迭代後的狀態,剛好落在 α|\alpha\rangle 軸上 ))

目標物的機率為P(target)P(|target\rangle)sin2Gr\sin^2{G^r}

maxsin2(Gr)maxsin(Gr)1Gr=(2r+1)θ2=π2\max \sin^2({G^r}) \Rightarrow \max \sin({G^r}) \Rightarrow 1 \Rightarrow G^r = (2r+1)\frac{\theta}{2} = \frac{\pi}{2}

ψ=(ψψ)ψ=ψψψ|\psi\rangle = (|\psi'\rangle\langle\psi'|)|\psi\rangle = \langle\psi'|\psi\rangle|\psi'\rangle

cosθ2ψ=ψ\cos\frac{\theta}{2}|\psi'\rangle = |\psi\rangle

cosθ2=ψψ=(2n1)×12n1×12n=2n12n\cos\frac{\theta}{2} = \langle\psi'|\psi\rangle = (2^n-1)\times\sqrt{\frac{1}{2^{n}-1}}\times\sqrt{\frac{1}{2^n}} = \sqrt{\frac{2^{n}-1}{2^n}}

(cos2+sin2=1)(\cos^2 + \sin^2 = 1)

sinθ2=12n\sin\frac{\theta}{2} = \sqrt{\frac{1}{2^n}}

θ2=sin112n\frac{\theta}{2} = \sin^{-1}\sqrt{\frac{1}{2^n}}

Gr=(2r+1)sin112n=π2G^r = (2r+1)\sin^{-1}\sqrt{\frac{1}{2^n}} = \frac{\pi}{2}nn 大時,sin112n12n\sin^{-1}\sqrt{\frac{1}{2^n}} \approx \sqrt{\frac{1}{2^n}}

r=π42nr = \frac{\pi}{4}\sqrt{2^n}

3 測量

最後做完以上步驟,正確率也將高達9x%,這時對他做測量,會有高機率找到你要的東西。

由於 n=log2Nn = \log_2N 所以說,這個演算法的複雜度為:O(π4N)=O(N)O(\frac{\pi}{4}\sqrt{N}) = O(\sqrt{N})

Code:
Grover’s Algorithm

Reference:
Solving Linear Systems of Equations by Gaussian Elimination Method Using Grover’s
Search Algorithm

An Introduction to Quantum Computing, Without the Physics
Quantiki