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

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

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

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

0 引 言

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

以上研究成果是建立在所有待檢索元素重要性無差異基礎上的。事實上，待檢索的部分信息間是可能存在一些重要性差別的。……