基于固定目標權重的量子部分搜索算法

摘 要： 針對現有量子部分搜索算法均未考慮目標對象重要性的差異，提出了一種對已分配權重的目標對象進行搜索的量子部分搜索算法。分析GRK算法的結構特點，構建能夠保持Grover算法原有性質的含有目標權重信息的量子疊加態算子，分析算法要達到最優時的匹配條件。仿真實驗表明，該算法能夠根據權重信息，成功搜索到目標元素。

關鍵詞： 量子部分搜索； 量子疊加態算子； 權重信息； 量子計算

中圖分類號： TN911?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2013）10?0087?03

0 引 言

Grover量子搜索算法由于其能夠高效的實現對在未整理數據庫中對滿足一定條件的目標進行成功搜索問題，并相對于經典搜索算法實現了二次加速，從誕生之日起，就在量子信息領域受到了廣泛關注，且后又被證明為最優的量子搜索算法[1]。故如何優化Grover算法，提高其搜索效率成為量子搜索算法研究的一個熱點。2005年，Grover和Radhakrishnan首先提出了利用量子計算并行性質，查找目標元素部分信息的量子部分搜索算法（GRK算法）[2]，將該領域的研究引向更深層次。之后，Korepin等人證明GRK部分搜索算法是最優部分搜索算法[3?5]；Byung?soo Choi等提出多目標元素平均分布在多目標塊中且成功率達到1的GRK算法[6?7]，李彥波等在此基礎上提出了更一般的多目標任意分布的GRK算法[8?9]，并分析了理論上該算法相比Grover量子經典算法節省迭代次數的上限。

以上研究成果是建立在所有待檢索元素重要性無差異基礎上的。事實上，待檢索的部分信息間是可能存在一些重要性差別的。基于此，在事先確定目標元素權重系數前提下，提出一種基于固定目標元素權重系數的量子部分搜索算法，能夠以權重系數相關的概率成功搜索到指定目標元素所在數據段。

（2）GRK算法過程描述

1.2 算法分析

2 基于固定權重的量子部分搜索算法

對以上數據進行分析可知，在目標態處于其他分布狀況時，本文算法結果也是可信的，在保證不同權重目標元素可成功檢出的前提下，未對標準GRK算法其他性質產生任何改變。

4 結 語

本文首先介紹了GRK算法的迭代過程，分析了

GRK算法的結構特點。在此基礎上為目標態引入了權

（下轉第93頁）

重系數，提出了基于該辦法的固定目標權重的量子搜索算法。算法能夠成功搜索到目標塊，并能夠以權重值的概率有效的區別目標元素間的重要性差異。通過仿真實驗，證明了算法的可靠性和有效性。

參考文獻

[1] ZALKA C. Grover’s quantum searching algorithm is optimal [J]. Phys. Rev A， 1999， 60（4）： 2746?2751.

[2] GROVER L K， RADHAKRISHNAN J. Is partial quantum search of a database any easier [C]// ACM Symposium on Parallel Algorithms and Architectures. Las Vegas， Nevada， USA： CAM， 2005： 1?15.

[3] KOREPIN V E， LIAO Jin?feng. Quest for fast partial search algorithm [J]. Information Processing， 2006， 5： 209?218.

[4] KOREPIN V E. Optimization of partial search [J]. Journal of Physics A： Math Gen.， 2005， 38： 731?738.

[5] KOREPIN V E， GROVER L K. Simple algorithm for partial quantum search [J]. Quantum Information Processing， 2006， 5（3）： 209?226.

[6] CHOI B S， KOREPIN V E. Quantum partial search of a database with several target items [J]. Quantum Information Processing， 2007， 97（6）： 1?13.

[7] CHOI B S， THOMAS A W， SAMUEL L B. Sure success partial search [J]. Quantum Information Processing， 2007， 6（1）： 1?8.

[8] 李彥波，周正威，鮑皖蘇，等.含有多目標的量子部分搜索：目標被非平均分配在兩塊中[J].量子光學學報，2008，14（3）：282?288.

[9] 鐘普查.量子搜索算法研究[D].鄭州：鄭州信息工程大學，2009.

[10] 馬穎，樊養余，田維堅，等.基于固定目標權重的量子搜索算法[J].計算機應用研究，2013，30（1）：155?157.