基于自適應相位匹配量子計算的求核算法

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

(南昌大學a.信息工程學院；b.圖書館，江西 南昌 330031)

以上的改進策略均不能保證100%的成功概率。該研究提出一種自適應匹配相位角度的策略，并將改進策略應用于粗糙集的核屬性求解。通過仿真實驗，提出的策略能夠在任意核屬性占比情況下都能以100%的概率得到核屬性。

1 相關研究

1.1 Grover算法

Grover算法是通過一系列的酉變換作用于等權重疊加態直至目標分量量子態的概率幅第一次到達峰值的過程。在這個過程中，目標分量量子態的概率幅被不斷增大，非目標分量量子態的概率幅被不斷削減。

設待搜索空間有N=2n個元素，所有分量以疊加態存放在n個量子比特中，Grover算法的簡要示意圖則表示為圖1。

如圖1所示，G算子包含Ga和Gs兩個子算子。Ga算子可以使目標分量實現π的相位翻轉。Gs算子隨后使所有分量進行均值翻轉。在規定次數內，目標分量的概率幅隨著G算子的迭代而不斷增大。

1.2 粗糙集核屬性

1982年Pawlak[12]提出粗糙集理論用于刻畫數據的不完備性和不精確性。粗糙集的核屬性是粗糙集理論中最關鍵的概念，是各種屬性約簡算法的先決條件。粗糙集核屬性的定義如下：

設S=(U，A，V，f)是一個粗糙集，對于任意屬性子集B?A，IND(B)表示由B確定的二元不可區分關系。那么，對于?a∈A，如果IND(A-{a})≠IND(A)，則稱a是A的核屬性。

2 自適應相位匹配Grover算法

針對現有Grover算法的局限性，提出一種自適應相位匹配量子搜索算法。改進算法的示意圖如下：

如圖2所示，對應于經典Grover算法，改進算法將迭代次數改為T′，將算子G改為算子G′。下面對T′和G′的確定方法進行詳細分析。

2.1 改進算法的迭代次數T′

這里先分析經典Grover算法迭代次數的求解方法，然后結合改進算法的特點給出T′的取值方法。

2.1.1 經典算法的完美迭代次數

經典Grover算法的搜索過程實際可以看作是用一系列的幺正矩陣去與一個每個維度上的值都相同且模為1的N維向量相乘，最后希望得到的結果是不斷提升解對應維度上的值和壓縮非解維度上的值。單從線性代數的角度上看，假設不要求迭代次數為正整數，那么目標解集是一定可以以100%的概率得到的。為了研究方便，我們假設上面講的這個迭代次數為完美迭代次數，并結合經典Grover算法，給出定義如下:

定義1設目標分量個數在總分量個數中占比為λ；那么，定義經典Grover算法的完美迭代次數為：

Tpft是根據令經過處理后的疊加態與目標分量的垂直向量成90度夾角(即目標分量的概率幅為1)得到的。但實際情況下，小數次的迭代次數是不可能實現的。從定義1中可以看出隨著λ的變化，Tpft有可能為正整數。Tpft為正整數時，那么說明這樣的次數是可以執行的。

2.1.2 提出算法的迭代次數

如同經典算法一樣，自適應相位匹配量子搜索的迭代次數也是至關重要的。這里先給出一個關于迭代次數的定理，然后確定提出算法的迭代次數。

定理1當且僅當迭代次數t滿足t≥Tpft時，存在相位角度φ，使得目標分量的概率幅為1。

證明經典Grover算法的相位角度為π，而相位角度π(π與-π等價)是使得疊加態與目標分量值平面的垂直矢量能產生最大夾角的相位。也就是說，π(或-π)是使得疊加態最快靠近目標分量值平面的相位角度。Tpft是經典Grover算法(即φ=π，-π在產生的夾角大小方面與π等價)在理論上第一次疊加態到達目標分量值平面的迭代次數，但Tpft在絕大多數情況下都是小數，在實際中無法實現。因此，僅當存在整數次迭代次數t，且滿足t≥Tpft時，才存在相位角度φ使得疊加態到達目標分量值平面。

證畢。

通過定理1可知，只要滿足t≥Tpft，那么就存在相位角度φ使得經過算子處理后的目標分量的概率幅等于1。在算法的設計中，迭代次數越少自然帶來的計算復雜度越小，而迭代次數又必須是整數次。因此，改進算法的迭代次數可對Tpft向上取整得到，即T′=CEIL(Tpft)，其中CEIL()為向上取整函數。

經典量子搜索的迭代次數是對Tpft四舍五入取整，提出算法迭代次數T′是對Tpft向上取整。因此，提出算法的迭代次數最多比經典量子搜索算法的迭代次數多一次。

2.2 改進算法算子G′

G′算子也包含兩個子算子Ga′和Gs′，表達式如公式(1)和公式(2)。

Ga′=I-(1-eiφ′)|a>

(1)

Gs′=(1-eiφ′)|s>

(2)

可以看出，只要求解出相位角度φ′就可以確定G′算子。假設j次G′算子迭代后得到的疊加態中各目標分量的概率幅為aj，各非目標分量的概率幅為bj，j為自然數。

首先，根據總分量的個數N，可以得出初始狀態下a0，b0的表達式如公式(3)所示。

(3)

再者，根據目標分量占比λ、Ga′和Gs′的表達式，j+1次G′算子迭代后，aj+1和bj+1與aj和bj總存在公式(4)和公式(5)所示的關系。

aj+1=-λei2φ′aj-(1-λ)eiφ′aj-(1-λ)eiφ′bj+(1-λ)bj

(4)

bj+1=-λei2φ′aj+λeiφ′aj-(1-λ)eiφ′bj-λbj

(5)

上一節已經證明改進算法在迭代T′次后，存在相位角度φ使得疊加態到達目標分量值平面，即使得bT=0。結合公式(3)、(4)和(5)就可求出相位角度φ′，進而確定算子G′。

2.3 算法描述

通過上面的分析得出的迭代次數、算法的相位角度，自適應相位匹配Grover算法可以描述為:

(1) 根據目標分量個數在總分量個數中的占比求出完美迭代次數Tpft

(2) 對Tpft向上取整求出算法迭代次數T′

(3) 結合公式(3)、(4)、(5)得出bT表達式，令bT=0，求出相位角度φ′

(4) 根據φ′構建算子Ga′和Gs′

(5) 構建等權重疊加態|s>

(6) 將Ga′算子和Gs′算子T′次作用于|s>

(7) 測量得到的疊加態

3 基于改進量子計算的求核算法

3.1 構建黑盒

設S=(U，A，V，f)，a∈A是待求核粗糙集，其屬性個數為N，核屬性個數為M。要將自適應相位匹配Grover算法應用到S的求核上，我們可以把量子算法的每一個分量x和粗糙集的各個屬性做一個映射，既x→a。對應改進的Grover算法，迭代算子中Ga′的判別函數修改為：

3.2 核屬性個數確定及算法描述

粗糙集S中的核屬性個數M可以通過結合Shor算法和Grover算法的量子計算算法[13]確定，隨后便可以確定核屬性個數在屬性總個數中的占比，接著算法的步驟如下：

(1) 確定完美迭代次數Tpft

(2) 求解迭代次數T′以及相位角度φ′

(3) 構建算子Ga′和Gs′

(4) 構建等權重疊加態|s>

(5) 將Ga′和Gs′算子T′次作用于|s>

(6) 測量得到的疊加態

4 仿真實驗及分析

4.1 數據集

為了詳細地體現整體分布情況，實驗者自行構造數據集如：構造一個32行32列的矩陣，矩陣的斜對角線上由整數0至31構成，矩陣其它位置的數值均為0。

數據集Ik由上述矩陣的第一行至第k+1行構成，其中，k=1，2，3，…，31。由此，上述矩陣可以產生31個數據集(數據集I1，I2，…，I31)。顯而易見，數據集Ik的核屬性集包含第二至第k+1列共k列屬性。

4.2 仿真環境

系統：64位Windows7系統、2GB內存、IntelCorei5處理器。

軟件：Matlab2012B。

4.3 測試結果及分析

實驗將本文算法與基于經典Grover以及文獻[5]中的固定相位Grover算法進行比較。實驗得到的數據被繪成圖3和圖4。

從圖3中可以看出：經典Grover算法在核屬性不超過半數時總能以0.5以上的概率得到目標分量，當核屬性超過半數時算法失效；固定相位Grover算法在得到目標概率上明顯優于經典Grover算法，總能以0.9以上的概率得到目標分量；而本文提出的算法總能以1的概率得到目標分量?？偟膩碚f，在解分量概率方面，本文提出的算法明顯優于經典Grover算法和固定相位Grover算法。

從圖4中可以看出：經典Grover的算子迭代次數最少；固定相位算法的算子迭代次數要明顯高于經典Grover算法；本文算法的算子迭代次數，明顯低于固定相位算法的算子迭代次數，略高于經典Grover算法的算子迭代次數。

4.4 小節

該研究將提出的算法和兩種已見算法進行了對比實驗。從實驗中可以得出，在目標分量概率方面，本文的算法總能以100%的概率得到目標分量，優于其它兩種算法；在算子迭代次數方面，本文算法略次于經典算法，僅在部分情況下比經典Grover算法多迭代一次，但明顯優于固定相位Grover算法。

5 結束語

該研究首先提出一種自適應相位匹配策略來改進Grover算法，使得改進策略在迭代次數不超過經典算法1次的情況下總能以100%的概率得到目標分量；然后將改進策略應用于粗糙集的核屬性求解上，并得到了平方根的加速效果。

雖然該研究在粗糙集核屬性的求解上有良好的效果，但卻不能解決粗糙集屬性約簡的問題。未來的研究方向主要為如何將量子算法應用于粗糙集的屬性約簡。