基于固定目標(biāo)權(quán)重的量子部分搜索算法

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

關(guān)鍵詞： 量子部分搜索； 量子疊加態(tài)算子； 權(quán)重信息； 量子計(jì)算

中圖分類(lèi)號(hào)： TN911?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）10?0087?03

0 引 言

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

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

（2）GRK算法過(guò)程描述

1.2 算法分析

2 基于固定權(quán)重的量子部分搜索算法

對(duì)以上數(shù)據(jù)進(jìn)行分析可知，在目標(biāo)態(tài)處于其他分布狀況時(shí)，本文算法結(jié)果也是可信的，在保證不同權(quán)重目標(biāo)元素可成功檢出的前提下，未對(duì)標(biāo)準(zhǔn)GRK算法其他性質(zhì)產(chǎn)生任何改變。

4 結(jié) 語(yǔ)

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

GRK算法的結(jié)構(gòu)特點(diǎn)。在此基礎(chǔ)上為目標(biāo)態(tài)引入了權(quán)

（下轉(zhuǎn)第93頁(yè)）

重系數(shù)，提出了基于該辦法的固定目標(biāo)權(quán)重的量子搜索算法。算法能夠成功搜索到目標(biāo)塊，并能夠以權(quán)重值的概率有效的區(qū)別目標(biāo)元素間的重要性差異。通過(guò)仿真實(shí)驗(yàn)，證明了算法的可靠性和有效性。

參考文獻(xiàn)

[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] 李彥波，周正威，鮑皖蘇，等.含有多目標(biāo)的量子部分搜索：目標(biāo)被非平均分配在兩塊中[J].量子光學(xué)學(xué)報(bào)，2008，14（3）：282?288.

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

[10] 馬穎，樊養(yǎng)余，田維堅(jiān)，等.基于固定目標(biāo)權(quán)重的量子搜索算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（1）：155?157.