Grover 量子搜索算法的改進(jìn)

1、Grover 量子搜索算法的改進(jìn)2022/8/18之陶興亮、王樂12.2 使用局部擴(kuò)散算子的量子搜索算法2003年，英國伯明翰大學(xué)Younes提出了一種使用局部擴(kuò)散算子的搜索算法，該算法中算子的均值反轉(zhuǎn)操作僅在系統(tǒng)的一個(gè)局部子空間上執(zhí)行。理論推導(dǎo)和實(shí)驗(yàn)證明，該算法比基本Grover算法具有更優(yōu)良的性能，尤其適用于多目標(biāo)搜索。對于在N個(gè)元素中尋找M個(gè)目標(biāo)的搜索，其成功概率至少為84.72%。22.2.1 一步迭代搜索 對于擁有 個(gè)元素的無序數(shù)據(jù)搜索，一步迭代搜索的實(shí)施過程可分為4步，如下圖所示。.N量子比特1 qubit工作空間測量3具體步驟如下：(1) 準(zhǔn)備存儲(chǔ)器。準(zhǔn)備一個(gè)所有量子位處于|0態(tài)

2、的n+1位作為Oracle算子 的工作空間。此時(shí)系統(tǒng)狀態(tài)為(2)寄存器初始化。對于前n位量子位施加H門變換，將系統(tǒng)狀態(tài)變?yōu)?個(gè)狀態(tài)的均勻疊加態(tài)，即(3)應(yīng)用Oracle識(shí)別搜索問題的解，并將識(shí)別結(jié)果存儲(chǔ)在附加量子比特中，即(4)局部擴(kuò)散。首先定義一個(gè)局部擴(kuò)散算子Y，將其用于n+1位量子比特系統(tǒng)中，該算子可描述為其中向量|0的長度為4下面考慮將Y應(yīng)用于具有P個(gè)基本狀態(tài)的量子系統(tǒng)的情況。為便于敘述，該量子系統(tǒng)可以重寫為其中當(dāng)k為偶數(shù)時(shí) ，當(dāng)k為奇數(shù)時(shí) 。應(yīng)用Y后該量子系統(tǒng)變?yōu)?其中 是子空間 的幅度均值。上述結(jié)果表明，應(yīng)用局部擴(kuò)散算子Y的結(jié)果只是在子空間 上執(zhí)行均值翻轉(zhuǎn)，而對于子空間，僅僅只是改變

3、幅度的符號(hào)。記 為所有搜索問題的解集， 為所有非解的集合，由d式描述的 系統(tǒng)狀態(tài)可以描述為6將Y作用于 后，系統(tǒng)狀態(tài)更新為記 均值為 ，經(jīng)計(jì)算上式各系數(shù)為：7(5) 測量。經(jīng)過一步迭代搜索之后，搜索的成功概率為82.2.2 算法原理 當(dāng)Oracle算子 和局部擴(kuò)算算子Y作用于系統(tǒng)狀態(tài)時(shí)，就構(gòu)成了迭代算法。如前所述，系統(tǒng)在一次迭代之后的狀態(tài)如e式，經(jīng)過二次迭代后，系統(tǒng)更新情況如下： 應(yīng)用Oracle算子 后，將具有概率幅 的目標(biāo)態(tài)概率幅交換后，系統(tǒng)可描述為應(yīng)用局部擴(kuò)散算子Y作用后系統(tǒng)狀態(tài)變?yōu)橛?，?jīng)過計(jì)算上式中各系數(shù)分別為 9同理，三次迭代后系統(tǒng)狀態(tài)變?yōu)?0系統(tǒng)搜索的成功的概率為綜上所述，經(jīng)過q=2次迭代之后，系統(tǒng)狀態(tài)可描述為記。計(jì)算上式中各態(tài)系數(shù)可用遞推算式11系統(tǒng)的搜索的成功概率是當(dāng)q=2時(shí)，將g式改為解上述的迭代方程可得12其中y=cos，0=/2。由第二類切比雪夫多項(xiàng)式，上述三式可寫為13且滿足14 為確定以高概率獲得一個(gè)搜索目標(biāo)所需要的迭代步數(shù)，Younes給出了如下定理。 定理：若使得成功概率 =1，其中 是第二類切比雪夫多項(xiàng)式，y=cos且0=/2，則所需迭代步數(shù)為 。證