改進量子搜索算法及其在核屬性求解上的應用

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

南昌大學 信息工程學院，南昌 330031

1 引言

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

在Grover算法的應用方面，不少學者都進行了研究。彭宏等[2]的無線量子網絡路由算法可以在限定的步驟內計算出目標路徑；阮越等[3]將Grover算法融入主成分分析中，對原算法而言有著平方根的加速；孫國棟等[4]將Grover算法應用到求根問題上，將求根問題的時間復雜度降低到

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

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

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

2 基礎知識

2.1 Grover算法

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

圖1 Grover算法示意圖

如圖1所示，搜索空間為N,n為量子比特位個數，n與N滿足關系N=2n。G算子包含Ga和Gs兩個子算子。Ga算子可以實現對目標分量進行相位取反操作。Gs算子在目標分量取反以后再對所有分量進行均值翻轉。在特定次數內，逐次迭代G算子，目標分量的概率幅將不斷增大。

2.2 迭代次數自適應Grover算法

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

迭代次數自適應Grover算法利用了Grover算法的幾個特性：（1）Grover算法在迭代合適次數的酉算子后能夠首次達到峰值；（2）用于迭代的疊加態總相位和首次變為負值時，目標分量的概率幅首次達到最大值；（3）疊加態分量Z基下相位和正負性由X基下的++…+分量相位正負性所決定。

根據上述幾個特性，在每次迭代G算子時，都在Ga算子后面加一個Phase門來測量疊加態的總相位。若總相位為正，繼續迭代G算子；若總相位為負，則停止迭代G算子，然后對得到的疊加態進行測量。該算法改進的G算子簡要示意圖如圖2所示。

圖2 改進G算子示意圖

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

3 改進的量子搜索算法

用經典算法搜尋一個搜索空間中目標時，目標的占比越低，則意味著得到目標的概率越低。而在用Grover算法搜索時，目標的占比越低，反而得到目標的概率越高。利用Grover算法的這個特性，擴大搜索空間的方法可以用來改進迭代次數自適應Grover算法。下面提出并證明幾個定理，然后給出改進算法。

3.1 定理及證明

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

定理1T值相同的情況下，當Tpft-floor(Tpft)=0.5時，經過迭代算子作用后，疊加態中目標分量的概率幅達到極小值（floor()函數為向下取整函數）。

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

當T值相同，且0

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

證畢。

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

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

證畢。

3.2 改進算法描述

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

（1）制備n+2量子位的等權重疊加態，其中N=2n。

（2）迭代Ga算子。

（3）測量Phase門，若相位因子為正，順序執行；否則，跳轉至步驟（6）。

（4）迭代Gs算子。

（5）跳轉至步驟2。

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

（6）測量最終的疊加態。

4 改進算法在求核屬性上的應用

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

4.1 粗糙集核屬性

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

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

4.2 基于改進量子搜索的求核算法

要將改進量子搜索應用于求核問題，先要增加原粗糙集的屬性列數，再者就是要改進Ga算子中的判別函數。

4.2.1 增加屬性列

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

4.2.2 Ga算子改進

Grover算法中Ga算子首先實現一個函數功能 f(x)判別目標分量是否為要搜索的值。當判別函數判定是要搜索的值時，f(x)=1；否則，f(x)=0。然后再將區分出來的目標分量進行相位取反。

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

4.2.3 算法描述

設粗糙集S=(U,A,V,f),A中屬性列數正好為N。基于改進量子搜索的求核算法具體步驟如下：

（1）通過增加不改變原分類關系的屬性集，得到S′=(U,A+C,V,f)。A+C中的屬性個數正好為4N。

（2）制備n+2量子位的等權重疊加態s，其中中的4N個分量分別對應S′中4N個屬性列。

（3）迭代G'a算子。

（4）測量Phase門，若相位因子為正，順序執行；否則，跳轉至步驟（7）。

（5）迭代Gs算子。

（6）跳轉至步驟（3）。

（7）測量最終的疊加態。

5 仿真實驗

仿真實驗將改進算法、Grover算法和文獻[14]的算法都來進行對粗糙集的核屬性求解，選取的數據集為UCI數據集，選取的平臺為Matlab。仿真實驗的結果充分說明了改進提出算法的有效性和優勢。

5.1 數據集

實驗選取的數據集為UCI數據集，具體數據集的情況如表1所示。

表1 UCI數據集

5.2 測試結果及分析

5.2.1 測試結果

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

表2 UCI數據集實驗結果

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

5.2.2 結果分析

通過UCI數據集的對比實驗，改進算法雖然在整體上優于Grover算法以及文獻[14]算法，但在某些情況下，獲得目標分量的概率反而不如對比的兩個算法。下面將各個算法的表現繪制在同一張圖上來分析改進算法的優勢及劣勢。Grover算法、文獻[14]算法及改進算法在目標分量占比不同情況下獲得目標分量概率分布如圖3所示。

圖3 目標分量占比與解概率的關系

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

5.3 小結

本節對提出的改進算法和已有的兩種算法進行了對比實驗。從實驗中可以得出，改進算法不僅實現了迭代次數的自適應，且在整體表現上優于已有的兩種算法。

6 結束語

量子搜索算法的一個難點在于目標分量占比的確定，而目標分量占比是許多量子算法用來計算算法迭代次數和相位角度的重要參數。學者提出了迭代次數自適應的算法有效地繞過了求解目標分量占比的問題，但在獲得目標分量概率的表現上并沒有任何提升。改進的基于迭代次數自適應量子搜索，通過擴大搜索空間，有效地提高了迭代自適應量子搜索獲得目標的概率。

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