基于自適應(yīng)相位匹配量子計(jì)算的求核算法

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

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

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

1 相關(guān)研究

1.1 Grover算法

Grover算法是通過(guò)一系列的酉變換作用于等權(quán)重疊加態(tài)直至目標(biāo)分量量子態(tài)的概率幅第一次到達(dá)峰值的過(guò)程。在這個(gè)過(guò)程中，目標(biāo)分量量子態(tài)的概率幅被不斷增大，非目標(biāo)分量量子態(tài)的概率幅被不斷削減。

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

如圖1所示，G算子包含Ga和Gs兩個(gè)子算子。Ga算子可以使目標(biāo)分量實(shí)現(xiàn)π的相位翻轉(zhuǎn)。Gs算子隨后使所有分量進(jìn)行均值翻轉(zhuǎn)。在規(guī)定次數(shù)內(nèi)，目標(biāo)分量的概率幅隨著G算子的迭代而不斷增大。

1.2 粗糙集核屬性

1982年P(guān)awlak[12]提出粗糙集理論用于刻畫(huà)數(shù)據(jù)的不完備性和不精確性。粗糙集的核屬性是粗糙集理論中最關(guān)鍵的概念，是各種屬性約簡(jiǎn)算法的先決條件。粗糙集核屬性的定義如下：

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

2 自適應(yīng)相位匹配Grover算法

針對(duì)現(xiàn)有Grover算法的局限性，提出一種自適應(yīng)相位匹配量子搜索算法。改進(jìn)算法的示意圖如下：

如圖2所示，對(duì)應(yīng)于經(jīng)典Grover算法，改進(jìn)算法將迭代次數(shù)改為T(mén)′，將算子G改為算子G′。下面對(duì)T′和G′的確定方法進(jìn)行詳細(xì)分析。

2.1 改進(jìn)算法的迭代次數(shù)T′

這里先分析經(jīng)典Grover算法迭代次數(shù)的求解方法，然后結(jié)合改進(jìn)算法的特點(diǎn)給出T′的取值方法。

2.1.1 經(jīng)典算法的完美迭代次數(shù)

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

定義1設(shè)目標(biāo)分量個(gè)數(shù)在總分量個(gè)數(shù)中占比為λ；那么，定義經(jīng)典Grover算法的完美迭代次數(shù)為：

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

2.1.2 提出算法的迭代次數(shù)

如同經(jīng)典算法一樣，自適應(yīng)相位匹配量子搜索的迭代次數(shù)也是至關(guān)重要的。這里先給出一個(gè)關(guān)于迭代次數(shù)的定理，然后確定提出算法的迭代次數(shù)。

定理1當(dāng)且僅當(dāng)?shù)螖?shù)t滿足t≥Tpft時(shí)，存在相位角度φ，使得目標(biāo)分量的概率幅為1。

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

證畢。

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

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

2.2 改進(jìn)算法算子G′

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

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

(1)

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

(2)

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

首先，根據(jù)總分量的個(gè)數(shù)N，可以得出初始狀態(tài)下a0，b0的表達(dá)式如公式(3)所示。

(3)

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

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

(4)

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

(5)

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

2.3 算法描述

通過(guò)上面的分析得出的迭代次數(shù)、算法的相位角度，自適應(yīng)相位匹配Grover算法可以描述為:

(1) 根據(jù)目標(biāo)分量個(gè)數(shù)在總分量個(gè)數(shù)中的占比求出完美迭代次數(shù)Tpft

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

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

(4) 根據(jù)φ′構(gòu)建算子Ga′和Gs′

(5) 構(gòu)建等權(quán)重疊加態(tài)|s>

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

(7) 測(cè)量得到的疊加態(tài)

3 基于改進(jìn)量子計(jì)算的求核算法

3.1 構(gòu)建黑盒

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

3.2 核屬性個(gè)數(shù)確定及算法描述

粗糙集S中的核屬性個(gè)數(shù)M可以通過(guò)結(jié)合Shor算法和Grover算法的量子計(jì)算算法[13]確定，隨后便可以確定核屬性個(gè)數(shù)在屬性總個(gè)數(shù)中的占比，接著算法的步驟如下：

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

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

(3) 構(gòu)建算子Ga′和Gs′

(4) 構(gòu)建等權(quán)重疊加態(tài)|s>

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

(6) 測(cè)量得到的疊加態(tài)

4 仿真實(shí)驗(yàn)及分析

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

為了詳細(xì)地體現(xiàn)整體分布情況，實(shí)驗(yàn)者自行構(gòu)造數(shù)據(jù)集如：構(gòu)造一個(gè)32行32列的矩陣，矩陣的斜對(duì)角線上由整數(shù)0至31構(gòu)成，矩陣其它位置的數(shù)值均為0。

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

4.2 仿真環(huán)境

系統(tǒng)：64位Windows7系統(tǒng)、2GB內(nèi)存、IntelCorei5處理器。

軟件：Matlab2012B。

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

實(shí)驗(yàn)將本文算法與基于經(jīng)典Grover以及文獻(xiàn)[5]中的固定相位Grover算法進(jìn)行比較。實(shí)驗(yàn)得到的數(shù)據(jù)被繪成圖3和圖4。

從圖3中可以看出：經(jīng)典Grover算法在核屬性不超過(guò)半數(shù)時(shí)總能以0.5以上的概率得到目標(biāo)分量，當(dāng)核屬性超過(guò)半數(shù)時(shí)算法失效；固定相位Grover算法在得到目標(biāo)概率上明顯優(yōu)于經(jīng)典Grover算法，總能以0.9以上的概率得到目標(biāo)分量；而本文提出的算法總能以1的概率得到目標(biāo)分量?？偟膩?lái)說(shuō)，在解分量概率方面，本文提出的算法明顯優(yōu)于經(jīng)典Grover算法和固定相位Grover算法。

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

4.4 小節(jié)

該研究將提出的算法和兩種已見(jiàn)算法進(jìn)行了對(duì)比實(shí)驗(yàn)。從實(shí)驗(yàn)中可以得出，在目標(biāo)分量概率方面，本文的算法總能以100%的概率得到目標(biāo)分量，優(yōu)于其它兩種算法；在算子迭代次數(shù)方面，本文算法略次于經(jīng)典算法，僅在部分情況下比經(jīng)典Grover算法多迭代一次，但明顯優(yōu)于固定相位Grover算法。

5 結(jié)束語(yǔ)

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

雖然該研究在粗糙集核屬性的求解上有良好的效果，但卻不能解決粗糙集屬性約簡(jiǎn)的問(wèn)題。未來(lái)的研究方向主要為如何將量子算法應(yīng)用于粗糙集的屬性約簡(jiǎn)。