謝旭明，段隆振，邱桃榮，楊幼鳳

南昌大學(xué) 信息工程學(xué)院，南昌 330031

1 引言

量子計(jì)算能夠并行地搜索待求解空間。由于這個(gè)特性，大量學(xué)者對(duì)量子計(jì)算進(jìn)行研究。然而，量子計(jì)算并不能確定地得到待求解問題的解，而是以一定的概率得到解。因此，如何提高得到目標(biāo)分量的概率成為量子計(jì)算的一個(gè)重要研究方向。Grover算法[1]是經(jīng)典的量子算法之一，實(shí)現(xiàn)了無序數(shù)據(jù)庫搜索問題的平方根級(jí)加速。自提出以來，Grover算法的普遍適用性使其得到了廣泛的關(guān)注。

在Grover算法的應(yīng)用方面，不少學(xué)者都進(jìn)行了研究。彭宏等[2]的無線量子網(wǎng)絡(luò)路由算法可以在限定的步驟內(nèi)計(jì)算出目標(biāo)路徑；阮越等[3]將Grover算法融入主成分分析中，對(duì)原算法而言有著平方根的加速；孫國棟等[4]將Grover算法應(yīng)用到求根問題上，將求根問題的時(shí)間復(fù)雜度降低到

在Grover算法的效率提升方面，也有許多學(xué)者進(jìn)行了深入的探索。Grover算法比較突出的問題是：當(dāng)目標(biāo)分量占比超過1/4時(shí)，算法得到目標(biāo)分量的概率急劇下降；且當(dāng)目標(biāo)分量占比過半時(shí)，算法會(huì)失效。針對(duì)這些問題，學(xué)者們提出了許多改進(jìn)的方法。張煜東等[5]提出將原算法的搜索范圍擴(kuò)大一倍，從而使得目標(biāo)分量占比一直處于半數(shù)以下，有效地解決了算法失效的問題，但仍不能一直保持高概率地得到目標(biāo)分量；Grover[6]將原算法的固定相位π改變成固定相位，從而使得整體得到目標(biāo)分量的概率得到了提升；Younes等[7]利用局部擴(kuò)散算法來改進(jìn)Grover算法，使得最低成功概率提高至84.72%；Li等[8]提出新的相位匹配條件，使得當(dāng)目標(biāo)分量占比超過1/3時(shí)，一次迭代就能達(dá)到高于25/27的成功率；Zhong等[9]將相位定為1.018，算法可以將成功概率保持在93.43%以上；Li等[10]將旋轉(zhuǎn)相位改為0.1π，使得算法的成功率高于99.38%；Younes[11]后續(xù)又把旋轉(zhuǎn)相位改為1.926 84π，新算法的成功概率至少為93.58%；Ma等[12]提出一種在四個(gè)相位上都改變的算法，一次迭代時(shí)，算法使得在目標(biāo)分量占比高于1/3的情況下獲得97.82%以上的成功率；李盼池等[13]在目標(biāo)分量占比超過時(shí)自適應(yīng)地算出相位旋轉(zhuǎn)角度，使得改進(jìn)的算法在這樣的情況下能以概率1得到目標(biāo)分量，但當(dāng)占比小于時(shí)，仍然采用Grover算法，此時(shí)的成功率等同于Grover算法。

美中不足的是，以上的改進(jìn)策略都只能在目標(biāo)分量占比已經(jīng)確定的情況下實(shí)施，但求解目標(biāo)分量占比也需要不少的運(yùn)算。針對(duì)這個(gè)問題，朱皖寧等[14]提出了一種迭代次數(shù)自適應(yīng)量子搜索策略，該策略在目標(biāo)分量占比未知的情況下也可以順利地進(jìn)行量子搜索。雖然這個(gè)算法可以在目標(biāo)分量占比未知的情況下自適應(yīng)地停止算法，但Grover算法存在的部分效率低下和目標(biāo)分量占比過半時(shí)的失效問題并沒有在該算法中得到改善。

本文主要研究內(nèi)容是：（1）改進(jìn)迭代次數(shù)自適應(yīng)Grover算法；（2）將改進(jìn)的算法來仿真計(jì)算粗糙集的核屬性。仿真結(jié)果表明，改進(jìn)的算法有效地解決了之前算法部分效率低下和失效的問題。

2 基礎(chǔ)知識(shí)

2.1 Grover算法

Grover算法主要是由酉變換反復(fù)迭代多次組成，其簡要示意圖如圖1。

圖1 Grover算法示意圖

如圖1所示，搜索空間為N,n為量子比特位個(gè)數(shù)，n與N滿足關(guān)系N=2n。G算子包含Ga和Gs兩個(gè)子算子。Ga算子可以實(shí)現(xiàn)對(duì)目標(biāo)分量進(jìn)行相位取反操作。Gs算子在目標(biāo)分量取反以后再對(duì)所有分量進(jìn)行均值翻轉(zhuǎn)。在特定次數(shù)內(nèi)，逐次迭代G算子，目標(biāo)分量的概率幅將不斷增大。

2.2 迭代次數(shù)自適應(yīng)Grover算法

Grover算法是建立在目標(biāo)分量占比已知的假設(shè)上。但實(shí)際問題中，目標(biāo)分量占比也是需要去求解的。朱皖寧等[14]提出的迭代次數(shù)自適應(yīng)Grover算法在目標(biāo)分量占比未知的情況下也能求解出目標(biāo)分量。

迭代次數(shù)自適應(yīng)Grover算法利用了Grover算法的幾個(gè)特性：（1）Grover算法在迭代合適次數(shù)的酉算子后能夠首次達(dá)到峰值；（2）用于迭代的疊加態(tài)總相位和首次變?yōu)樨?fù)值時(shí)，目標(biāo)分量的概率幅首次達(dá)到最大值；（3）疊加態(tài)分量Z基下相位和正負(fù)性由X基下的++…+分量相位正負(fù)性所決定。

根據(jù)上述幾個(gè)特性，在每次迭代G算子時(shí)，都在Ga算子后面加一個(gè)Phase門來測(cè)量疊加態(tài)的總相位。若總相位為正，繼續(xù)迭代G算子；若總相位為負(fù)，則停止迭代G算子，然后對(duì)得到的疊加態(tài)進(jìn)行測(cè)量。該算法改進(jìn)的G算子簡要示意圖如圖2所示。

圖2 改進(jìn)G算子示意圖

在目標(biāo)分量占比未知的情況下，迭代次數(shù)自適應(yīng)Grover算法實(shí)現(xiàn)了迭代次數(shù)的自主控制。但該算法依然存在著兩個(gè)比較明顯的缺陷：一方面，該算法并沒有解決目標(biāo)分量占比過半時(shí)的失效問題；另一方面，算法最終獲得目標(biāo)分量的概率在某些情況下并不是很高。針對(duì)出現(xiàn)的這兩個(gè)突出問題，該研究提出一種改進(jìn)策略，同時(shí)解決了失效和目標(biāo)分量概率不高的兩個(gè)問題。

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

用經(jīng)典算法搜尋一個(gè)搜索空間中目標(biāo)時(shí)，目標(biāo)的占比越低，則意味著得到目標(biāo)的概率越低。而在用Grover算法搜索時(shí)，目標(biāo)的占比越低，反而得到目標(biāo)的概率越高。利用Grover算法的這個(gè)特性，擴(kuò)大搜索空間的方法可以用來改進(jìn)迭代次數(shù)自適應(yīng)Grover算法。下面提出并證明幾個(gè)定理，然后給出改進(jìn)算法。

3.1 定理及證明

由公式（1）可以看出Tpft并不能保證每次都為整數(shù)，而非整數(shù)次的迭代次數(shù)在現(xiàn)實(shí)中是不可能實(shí)現(xiàn)的。Grover算法通過對(duì)Tpft四舍五入取整來確定算法的迭代次數(shù)T。下面基于Tpft提出幾個(gè)定理。

定理1T值相同的情況下，當(dāng)Tpft-floor(Tpft)=0.5時(shí)，經(jīng)過迭代算子作用后，疊加態(tài)中目標(biāo)分量的概率幅達(dá)到極小值（floor()函數(shù)為向下取整函數(shù)）。

證明 在Hilbert空間里，設(shè)初始等權(quán)重疊加態(tài)矢量與目標(biāo)分量值平面垂直矢量的夾角為那么，經(jīng)過迭代算子作用后的最終疊加態(tài)矢量與目標(biāo)分量值平面垂直矢量的夾角ω=(2T+1)θ。另，根據(jù)Tpft和θ的公式可知，當(dāng)Tpft越大時(shí)，ω的值就越小。

當(dāng)T值相同，且0

由此可以得出當(dāng)Tpft-floor(Tpft)=0.5時(shí)，目標(biāo)分量的概率幅為極小值。

證畢。

定理2目標(biāo)分量概率幅的極小值隨著T值增加而增大。

證明 定理1已經(jīng)證明當(dāng)T值相同且Tpft-floor(Tpft)=0.5時(shí)，目標(biāo)分量的概率幅達(dá)到極小值，此時(shí)T=Tpft+0.5。在出現(xiàn)極小值的情況下，結(jié)合公式（1）及可得出，Hilbert空間中初始疊加態(tài)與目標(biāo)分量值平面垂直矢量夾角為那么最終疊加態(tài)與目標(biāo)分量值平面垂直矢量的夾角則為其中T為正整數(shù)。由此得出，T值越大，則ω的值就越接近ω<π），即目標(biāo)分量的概率幅值sinω就越大。

證畢。

3.2 改進(jìn)算法描述

設(shè)搜索空間有N個(gè)分量，其中目標(biāo)分量的個(gè)數(shù)為M。根據(jù)上一節(jié)提出的定理，新算法將搜索空間增加至4N，這樣就可以保證目標(biāo)分量占比恒小于該研究提出的改進(jìn)迭代次數(shù)自適應(yīng)量子搜索具體步驟如下：

（1）制備n+2量子位的等權(quán)重疊加態(tài)，其中N=2n。

（2）迭代Ga算子。

（3）測(cè)量Phase門，若相位因子為正，順序執(zhí)行；否則，跳轉(zhuǎn)至步驟（6）。

（4）迭代Gs算子。

（5）跳轉(zhuǎn)至步驟2。

1973年英國Pugh等人改良的Child分級(jí)方案迄今一直被采用Child分級(jí)[8]是對(duì)肝臟儲(chǔ)備功能評(píng)估的判定。有研究者等[9]認(rèn)為Child分級(jí)標(biāo)準(zhǔn)是用來評(píng)價(jià)肝硬化患者肝臟儲(chǔ)備功能，可將患者病情程度量化評(píng)估，將肝硬化患者的5個(gè)指標(biāo)：一般情況、腹水、血清膽紅素、血清白蛋白濃度、凝血酶原時(shí)間，按不同狀態(tài)分三個(gè)層次，以1，2，3分記，將三個(gè)層次得分相加，視得分情況分A、B、C三級(jí)，得分越高說明肝臟儲(chǔ)備功能越差。

（6）測(cè)量最終的疊加態(tài)。

4 改進(jìn)算法在求核屬性上的應(yīng)用

粗糙集的核屬性求解問題與量子搜索算法解決的無序數(shù)據(jù)庫搜索問題有很大的相似。因此，將改進(jìn)算法應(yīng)用于粗糙集核屬性的求解問題上。下面簡單介紹一下粗糙集核屬性的概念，再給出基于改進(jìn)量子搜索的求核算法。

4.1 粗糙集核屬性

粗糙集理論[15]于1982年由Pawlak提出，是一種刻畫不完整性、不精確性、不完備性的數(shù)學(xué)理論。在粗糙集理論中，核屬性是至關(guān)重要的概念，是粗糙集屬性約簡的運(yùn)算核心。下面給出粗糙集核屬性的定義。

設(shè)S=(U,A,V,f)是一個(gè)粗糙集，對(duì)于任意屬性子集B?A,IND(B)表示由B確定的二元不可分辨關(guān)系。那么，對(duì)于?a∈A，如果IND(A-{a})=IND(A)，則可以認(rèn)定a在A中是多余的屬性（或稱為非核屬性）；否則，稱a是A的必要的屬性（或稱核屬性）。

4.2 基于改進(jìn)量子搜索的求核算法

要將改進(jìn)量子搜索應(yīng)用于求核問題，先要增加原粗糙集的屬性列數(shù)，再者就是要改進(jìn)Ga算子中的判別函數(shù)。

4.2.1 增加屬性列

設(shè)粗糙集S=(U,A,V,f),A中屬性列數(shù)正好為N。在改進(jìn)量子搜索的求核算法中，將粗糙集S擴(kuò)大為S′=(U,A+C,V,f),對(duì)于 ?c∈C ，存在 IND(A+C-{c})=IND(A+C)=IND(A)，且C中的屬性列數(shù)為3N。那么，此時(shí)屬性列數(shù)就正好滿足改進(jìn)量子搜索算法中4N的要求。

4.2.2 Ga算子改進(jìn)

Grover算法中Ga算子首先實(shí)現(xiàn)一個(gè)函數(shù)功能 f(x)判別目標(biāo)分量是否為要搜索的值。當(dāng)判別函數(shù)判定是要搜索的值時(shí)，f(x)=1；否則，f(x)=0。然后再將區(qū)分出來的目標(biāo)分量進(jìn)行相位取反。

求核問題中將原Ga算子改為G'a算子，相應(yīng)地判別函數(shù)f(x)改為判別函數(shù)f′(x)，使其滿足如公式（2）所示功能：

4.2.3 算法描述

設(shè)粗糙集S=(U,A,V,f),A中屬性列數(shù)正好為N?；诟倪M(jìn)量子搜索的求核算法具體步驟如下：

（1）通過增加不改變?cè)诸愱P(guān)系的屬性集，得到S′=(U,A+C,V,f)。A+C中的屬性個(gè)數(shù)正好為4N。

（2）制備n+2量子位的等權(quán)重疊加態(tài)s，其中中的4N個(gè)分量分別對(duì)應(yīng)S′中4N個(gè)屬性列。

（3）迭代G'a算子。

（4）測(cè)量Phase門，若相位因子為正，順序執(zhí)行；否則，跳轉(zhuǎn)至步驟（7）。

（5）迭代Gs算子。

（6）跳轉(zhuǎn)至步驟（3）。

（7）測(cè)量最終的疊加態(tài)。

5 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)將改進(jìn)算法、Grover算法和文獻(xiàn)[14]的算法都來進(jìn)行對(duì)粗糙集的核屬性求解，選取的數(shù)據(jù)集為UCI數(shù)據(jù)集，選取的平臺(tái)為Matlab。仿真實(shí)驗(yàn)的結(jié)果充分說明了改進(jìn)提出算法的有效性和優(yōu)勢(shì)。

5.1 數(shù)據(jù)集

實(shí)驗(yàn)選取的數(shù)據(jù)集為UCI數(shù)據(jù)集，具體數(shù)據(jù)集的情況如表1所示。

表1 UCI數(shù)據(jù)集

5.2 測(cè)試結(jié)果及分析

5.2.1 測(cè)試結(jié)果

仿真實(shí)驗(yàn)采用的數(shù)據(jù)集為UCI數(shù)據(jù)集，詳細(xì)信息已在表1中給出。由于Grover算法要求待求解分量的個(gè)數(shù)必須滿足2n要求，對(duì)于不滿足該條件的數(shù)據(jù)集，采用增加不影響分類劃分的屬性列來補(bǔ)齊。實(shí)驗(yàn)分別用Grover算法、文獻(xiàn)[14]算法以及改進(jìn)算法來求解上述數(shù)據(jù)集的核屬性。然后將對(duì)不同算法最終得到疊加態(tài)中目標(biāo)分量的總概率進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果如表2所示。

表2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從表2中可以看出：（1）文獻(xiàn)[14]算法未能解決Grover算法失效的問題。（2）在原算法不失效的情況下，文獻(xiàn)[14]算法最終得到目標(biāo)分量的概率和Grover算法一致。（3）改進(jìn)算法則不存在失效的問題；改進(jìn)算法得到目標(biāo)分量概率在大部分情況下優(yōu)于Grover算法和文獻(xiàn)[14]算法。

5.2.2 結(jié)果分析

通過UCI數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)，改進(jìn)算法雖然在整體上優(yōu)于Grover算法以及文獻(xiàn)[14]算法，但在某些情況下，獲得目標(biāo)分量的概率反而不如對(duì)比的兩個(gè)算法。下面將各個(gè)算法的表現(xiàn)繪制在同一張圖上來分析改進(jìn)算法的優(yōu)勢(shì)及劣勢(shì)。Grover算法、文獻(xiàn)[14]算法及改進(jìn)算法在目標(biāo)分量占比不同情況下獲得目標(biāo)分量概率分布如圖3所示。

圖3 目標(biāo)分量占比與解概率的關(guān)系

從圖3中可以看出：（1）Grover算法存在目標(biāo)占比過半失效問題，且當(dāng)目標(biāo)分量占比超過1/4時(shí)，獲得目標(biāo)分量的概率下降迅速。（2）雖然文獻(xiàn)[14]算法不用計(jì)算目標(biāo)分量占比，實(shí)現(xiàn)了迭代次數(shù)的自適應(yīng)，但算法在獲得目標(biāo)分量概率上的表現(xiàn)并沒有提高。Grover算法存在的失效問題和特定區(qū)間性能急劇下降問題在該算法中并沒有得到改善。（3）整體來看，改進(jìn)算法不存在失效問題，且獲得目標(biāo)分量的概率總能保持在85%以上。雖然在一些小區(qū)間內(nèi)，改進(jìn)算法的效率不如Grover算法和文獻(xiàn)[14]算法，但在這些區(qū)間內(nèi)算法的效率只是略低于兩個(gè)用于比較的算法。

5.3 小結(jié)

本節(jié)對(duì)提出的改進(jìn)算法和已有的兩種算法進(jìn)行了對(duì)比實(shí)驗(yàn)。從實(shí)驗(yàn)中可以得出，改進(jìn)算法不僅實(shí)現(xiàn)了迭代次數(shù)的自適應(yīng)，且在整體表現(xiàn)上優(yōu)于已有的兩種算法。

6 結(jié)束語

量子搜索算法的一個(gè)難點(diǎn)在于目標(biāo)分量占比的確定，而目標(biāo)分量占比是許多量子算法用來計(jì)算算法迭代次數(shù)和相位角度的重要參數(shù)。學(xué)者提出了迭代次數(shù)自適應(yīng)的算法有效地繞過了求解目標(biāo)分量占比的問題，但在獲得目標(biāo)分量概率的表現(xiàn)上并沒有任何提升。改進(jìn)的基于迭代次數(shù)自適應(yīng)量子搜索，通過擴(kuò)大搜索空間，有效地提高了迭代自適應(yīng)量子搜索獲得目標(biāo)的概率。

不足之處在于，雖然在整體上表現(xiàn)良好，該研究在某些區(qū)間里會(huì)出現(xiàn)效率略低于對(duì)比算法的問題。因此，未來的研究將致力于進(jìn)一步提升算法的性能。