Grover量子搜索算法的改進_第1頁
Grover量子搜索算法的改進_第2頁
Grover量子搜索算法的改進_第3頁
Grover量子搜索算法的改進_第4頁
Grover量子搜索算法的改進_第5頁
已閱讀5頁，還剩13頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

Grover量子搜尋算法的改進2023/8/23之陶興亮、王樂2.2使用局部集中算子的量子搜尋算法

2003年，英國伯明翰高校Younes提出了一種使用局部集中算子的搜尋算法，該算法中算子的均值反轉操作僅在系統的一個局部子空間上執行。理論推導和實驗證明，該算法比基本Grover算法具有更優良的性能，尤其適用于多目標搜尋。對于在N個元素中尋找M個目標的搜尋，其成功概率至少為84.72%。2.2.1一步迭代搜尋對于擁有個元素的無序數據搜尋，一步迭代搜尋的實施過程可分為4步，如下圖所示。….……N量子比特1qubit工作空間測量

簡略步驟如下： (1)籌備存儲器。籌備一個全部量子位處于|0>態的n+1位作為Oracle算子的工作空間。此時系統狀態為 (2)寄存器初始化。對于前n位量子位施加H門變換，將系統狀態變為個狀態的均勻疊加態，即 (3)應用Oracle識別搜尋問題的解，并將識別結果存儲在附加量子比特中，即 (4)局部集中。首先定義一個局部集中算子Y，將其用于n+1位量子比特系統中，該算子可描述為

其中向量|0>的長度為

下面考慮將Y應用于具有P個基本狀態的量子系統

的情況。為便于敘述，該量子系統可以重寫為

其中當k為偶數時

，當k為奇數時

。應用Y后該量子系統變為

其中

是子空間

的幅度均值。上述結果表明，應用局部集中算子Y的結果只是在子空間

上執行均值翻轉，而對于子空間

，僅僅只是轉變幅度的符號。

記為全部搜尋問題的解集，為全部非解的集合，由d式描述的系統狀態可以描述為

將Y作用于

后，系統狀態更新為

記均值為

，經計算上式各系數為：

(5)測量。經過一步迭代搜尋之后，搜尋的成功概率為

2.2.2算法原理當Oracle算子和局部擴算算子Y作用于系統狀態時，就構成了迭代算法。如前所述，系統在一次迭代之后的狀態如e式，經過二次迭代后，系統更新情況如下：應用Oracle算子后，將具有概率幅的目標態概率幅交換后，系統可描述為應用局部集中算子Y作用后系統狀態變為記 ，經過計算上式中各系數分別為

同理，三次迭代后系統狀態變為

系統搜尋的成功的概率為

綜上所述，經過q>=2次迭代之后，系統狀態可描述為

記

。計算上式中各態系數可用遞推算式

系統的搜尋的成功概率是

當q>=2時，將g式改為

解上述的迭代方程可得其中y=cosθ，0<θ<=π/2。由其次類切比雪夫多項式 ，上述三式可寫為

且滿意為確定以高概率獲得一個搜尋目標所需要的迭代步數，Younes給出了如下定理。定理：若使得成功概率 =1，其中是其次類切比雪夫多項式，y=cosθ且0<θ<=π/2，則所需迭代步數為 。證明

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論