量子計(jì)算 [4].ext + Long算法

2021-04-17 15:11 作者:nyasyamorina 0人讀過 | 我要投稿

Grover搜索算法詳解

Grover搜索算法分為兩步:? 制備均勻疊加態(tài) 和迭代某個(gè)過程,? 而迭代可以分為兩小步:? 作用相位黑盒和作用Grover擴(kuò)散算子.

而Grover算子為?? $G%3DW%5E%7B-1%7D(2%7C0%5En%5Crangle%5Clangle0%5En%7C-I)W$ ,? 其中W為Walsh-Hadamard變換 [或叫H變換也ok].

Walsh-Hadamard變換

H變換是一個(gè)廣義傅里葉變換,? 同時(shí)也是計(jì)算最簡單的廣義傅里葉變換,? N階H變換定義為:? $W_%7B2%5En%7D%3DH%5E%7B%5Cotimes%20n%7D$ ,??N = 2^n,? 其中 $H%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D%5Cbegin%7Bbmatrix%7D1%261%5C%5C1%26-1%5Cend%7Bbmatrix%7D$ ,? n為量子位數(shù)量.? 不難發(fā)現(xiàn)這個(gè)H矩陣定義與H門一致.? 所以H變換在量子計(jì)算表現(xiàn)為把H門作用在全部量子位上.? 并且因?yàn)镠門的逆也為H門,? 所以H變換的逆也為H變換.

既然H變換是廣義傅里葉變換,? 那么不難推測H變換實(shí)質(zhì)上也是在分析頻率.? 但是看到Grover算子中間的部分 $2%7C0%5En%5Crangle%5Clangle0%5En%7C-I$ ,? 只與變換后的第1個(gè)分量有關(guān),? 那么只需要關(guān)心變換的第1個(gè)分量:?? $W_N%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN%7D%7D%5Cbegin%7Bbmatrix%7D1%261%26%5Ccdots%261%5C%5C%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%5Cend%7Bbmatrix%7D$ ,? 可以看到變換的第1個(gè)分量與數(shù)據(jù)的總和有關(guān),? 或者說與均值有關(guān).

Grover算子

稍微把Grover算子扔進(jìn)人肉計(jì)算機(jī)里可以得到:?? $G%3D2P-I$ ,? 其中 $P_%7Bjk%7D%3D%5Cfrac%7B1%7D%7B2%5En%7D$ ,? 在不考慮輻角的情況下,? 也就是只有實(shí)數(shù)時(shí),? Grover算子實(shí)際上就是以系統(tǒng)的均值取對稱 [近似對稱].? 原論文里的兩個(gè)例子:

整個(gè)迭代

把正確答案寫為 $%7Cg%5Crangle$ ,? 錯(cuò)誤答案寫為 $%7Cb%5Crangle$ ,? 則定義 $%7CGood%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BM%7D%7D%5Csum_g%7Cg%5Crangle$ ?和 $%7CBad%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN-M%7D%7D%5Csum_b%7Cb%5Crangle$ ,? 其中M為全部正確答案的總數(shù),? N為全部答案的總數(shù) [一般N=2^n,?n為量子位數(shù)量].? 則均勻疊加態(tài)寫為? $H%5E%7B%5Cotimes%20n%7D%7C0%5En%5Crangle%3D%7C%2B%5En%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN%7D%7D%5Csum_%7Bx%3D0%7D%5E%7BN-1%7D%7Cx%5Crangle%3Dsin%5Ctheta%7CGood%5Crangle%2Bcos%5Ctheta%7CBad%5Crangle$ ,? 其中 $%5Ctheta%3Dsin%5E%7B-1%7D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D$ .

相位黑盒把所有正確答案的相位翻轉(zhuǎn),? 即? $U_f%3DI-2%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C%3D%7CBad%5Crangle%5Clangle%20Bad%7C-%7CGood%5Crangle%5Clangle%20Good%7C$

因?yàn)镚rover搜索算法是從均勻疊加態(tài)開始,? 所以在算法中任意時(shí)刻 $%7Cg%5Crangle$ 之間的系數(shù)都是一致的,? 同理 $%7Cb%5Crangle$ 之間也存在這樣的關(guān)系.? 設(shè)在某次迭代前系統(tǒng)狀態(tài)為 $%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle%2Bsin%5Cbeta%7CGood%5Crangle$ .??作用相位黑盒把正確答案的相位翻轉(zhuǎn):?? $U_f%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle-sin%5Cbeta%7CGood%5Crangle$ .? 此時(shí)系統(tǒng)的均值為? $avg%3D%5Cfrac%7B1%7D%7BN%7D(%5Csqrt%7BN-M%7Dcos%5Cbeta-%5Csqrt%7BM%7Dsin%5Cbeta)$ ,? 作用Grover算子后系統(tǒng)狀態(tài)為

$GU_f%7C%5CPsi%5Crangle%3D(cos(2%5Ctheta)cos%5Cbeta-sin(2%5Ctheta)sin%5Cbeta)%7CBad%5Crangle%2B(sin(2%5Ctheta)cos%5Cbeta%2Bcos(2%5Ctheta)sin%5Cbeta)%7CGood%5Crangle$

可以看到單次迭代的凈效應(yīng)是在? $%5C%7BO%3B%7CBad%5Crangle%2C%7CGood%5Crangle%5C%7D$ ?空間里逆時(shí)針旋轉(zhuǎn)了2θ.? 所以最佳迭代次數(shù) j 應(yīng)該使得系統(tǒng)狀態(tài)最接近 $%7CGood%5Crangle$ ,? 也就是與 $%7CBad%5Crangle$ 的夾角為π/2,? 即? $j%20%3D%20%5Cleft%5B%5Cfrac%7B%5Cfrac%7B%5Cpi%7D%7B2%7D-%5Ctheta%7D%7B2%5Ctheta%7D%5Cright%5D%3D%5Clfloor%5Cfrac%7B%5Cpi%7D%7B4%5Ctheta%7D%5Crfloor$ ,? 其中 $%5Clfloor%20%5Crfloor%20$ ?為向下取整 [floor].

詳細(xì)計(jì)算過程可以看本文結(jié)尾 -- 附1

Long算法

Long算法由龍桂魯教授提出,? 可以以概率1給出正確答案.

在Grover算法里,? 迭代次數(shù) j 由系統(tǒng)狀態(tài)在 $%5C%7BO%3B%7CBad%5Crangle%2C%7CGood%5Crangle%5C%7D$ ?空間里轉(zhuǎn)動(dòng)的角度2θ確定,? 但因?yàn)閖只能為正整數(shù),? 并且轉(zhuǎn)動(dòng)角度2θ不夠精細(xì),? 導(dǎo)致系統(tǒng)狀態(tài)幾乎不可能剛好等于 $%7CGood%5Crangle$ ,? 即不太可能以概率1給出正確結(jié)果.

Long算法的篇幅實(shí)在過長,? 需要深入了解的可以去看看原論文.? 這里稍微簡述一下.

拓展Grover搜索算法:? ?相位黑盒從 $U_f%3DI-2%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C$ ?拓展為 $I%2B(e%5E%7Bi%5Cphi%7D-1)%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C$ ,? 即從把正確答案的相位旋轉(zhuǎn)π改為旋轉(zhuǎn) $%5Cphi$ .??Grover算子從 $G%3DW(I-2%7C0%5En%5Crangle%5Clangle0%5En%7C)W$ ?拓展為 $W(I%2B(e%5E%7Bi%5Cvarphi%7D-1)%7C0%5En%5Crangle%5Clangle0%5En%7C)W$ ,? 即從把系統(tǒng)狀態(tài)沿著均值取對稱[近似]變?yōu)檠刂蛋严辔恍D(zhuǎn)φ.? 拓展后為了使算法有意義,? 需要滿足相位匹配條件 $%5Cphi%3D%5Cvarphi$ .

在Long算法里,? 需要指定迭代次數(shù) j,? 然后?求得旋轉(zhuǎn)相位 $%5Cvarphi%20%3D%202sin%5E%7B-1%7D%5Cleft(%5Cfrac%7Bsin(%5Cfrac%7B%5Cpi%7D%7B4j%2B2%7D)%7D%7Bsin%5Ctheta%7D%5Cright)$ ,? 為了確保相位有意義,? 迭代次數(shù)需要滿足? $j%3E%5Clfloor%5Cfrac%7B%5Cpi%7D%7B4%5Ctheta%7D-0.5%5Crfloor$ ,? 可以看到Long算法的迭代次數(shù)不可以比Grover算法里的迭代次數(shù)少,? 當(dāng) j 小于等于這個(gè)下限時(shí),? 旋轉(zhuǎn)相位φ為復(fù)數(shù),? 則算法失去意義.

修改本篇里的Grover算法為Long算法,? 需要注意的是,? 旋轉(zhuǎn)門需要在使用前確定,? 并且旋轉(zhuǎn)角度是由迭代次數(shù)確定,? 也就是需要在制作黑盒前就確定迭代次數(shù)

接下來修改黑盒s:

為了確保一致性,? GroverOperator和RunGroverSearching就沒有改名字了.? 因?yàn)長ong算法以概率1給出正確答案,? 所以并不需要檢查答案,? 則主體為

優(yōu)化輸出和結(jié)果檢查套用本篇里的就好.

G. L. Long $Grover%5C%3AAlgorithm%5C%3Awith%5C%3Azero%5C%3Atheoretical%5C%3Afailure%5C%3Arate$ (2001)

附1

作用相位黑盒后的系統(tǒng)狀態(tài)為

$U_f%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle-sin%5Cbeta%7CGood%5Crangle%3D%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D%5Csum_b%7Cb%5Crangle-%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D%5Csum_g%7Cg%5Crangle$

則均值為

$avg%3D%5Cfrac%7B1%7D%7BN%7D(%5Csum_b%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D-%5Csum_g%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D)%3D%5Cfrac%7B1%7D%7BN%7D(%5Csqrt%7BN-M%7Dcos%5Cbeta-%5Csqrt%7BM%7Dsin%5Cbeta)$

作用Grover算子 $G%3D2P-I$ 為

$GU_f%7C%5CPsi%5Crangle%3D(2avg-%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D)%5Csum_b%7Cb%5Crangle%2B(2avg%2B%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D)%5Csum_g%7Cg%5Crangle%3D(2%5Csqrt%7BN-M%7Davg-cos%5Cbeta)%7CBad%5Crangle%2B(2%5Csqrt%7BM%7Davg%2Bsin%5Cbeta)%7CGood%5Crangle$

$GU_f%7C%5CPsi%5Crangle%3D((1-%5Cfrac%7B2M%7D%7BN%7D)cos%5Cbeta-%5Cfrac%7B2%5Csqrt%7BM(N-M)%7D%7D%7BN%7Dsin%5Cbeta)%7CBad%5Crangle%2B(%5Cfrac%7B2%5Csqrt%7BM(N-M)%7D%7D%7BN%7Dsin%5Cbeta%2B(1-%5Cfrac%7B2M%7D%7BN%7D)sin%5Cbeta)%7CGood%5Crangle$

又因?yàn)? $sin%5Ctheta%3D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D%3Bcos%5Ctheta%3D%5Csqrt%7B%5Cfrac%7BN-M%7D%7BN%7D%7D$ ,? 使用倍角公式 $cos(2x)%3D1-2sin%5E2x%3Bsin(2x)%3D2cosxsinx$ 化簡得:

$GU_f%7C%5CPsi%5Crangle%3D(cos(2%5Ctheta)cos%5Cbeta-sin(2%5Ctheta)sin%5Cbeta)%7CBad%5Crangle%2B(sin(2%5Ctheta)cos%5Cbeta%2Bcos(2%5Ctheta)sin%5Cbeta)%7CGood%5Crangle$

標(biāo)簽：

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

量子計(jì)算 [4].ext + Long算法

量子計(jì)算 [4].ext + Long算法的評(píng)論 (共條)

你可能也喜歡這些文章

最新發(fā)布的文章

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

量子計(jì)算 [4].ext + Long算法

本文作者的其他文章

量子計(jì)算 [4].ext + Long算法的評(píng)論 (共 條)

你可能也喜歡這些文章

最新發(fā)布的文章

量子計(jì)算 [4].ext + Long算法的評(píng)論 (共條)