陸春悅,郭躬德,林 崧

(福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院,福建 福州 350117)

貝葉斯分類算法是一種常見的機(jī)器學(xué)習(xí)算法,它利用貝葉斯定理與聯(lián)合概率模型進(jìn)行分類預(yù)測,被廣泛應(yīng)用于文本分類. Shao[11]在2020年提出了基于塊編碼的量子貝葉斯分類算法(簡記為Shao算法). 該算法將塊編碼與貝葉斯分類相結(jié)合,實(shí)現(xiàn)了指數(shù)級加速. 然而,該算法僅僅適用于厄米矩陣. 本文針對這一問題進(jìn)行研究,提出了一種基于量子計(jì)數(shù)的貝葉斯二元分類算法. 該算法通過量子計(jì)數(shù)與相位估計(jì),快速得到能夠反映待分類數(shù)據(jù)屬于第k類別概率的相關(guān)值,獲取待分類數(shù)據(jù)所屬類別. 本文所提算法在低維特征空間中與經(jīng)典算法相比有著指數(shù)級加速,也可應(yīng)用于更為普遍的數(shù)據(jù)集.

1 背景知識(shí)

1.1 樸素貝葉斯分類算法

(1)

(2)

因此,貝葉斯分類過程要求計(jì)算概率,

(3)

(4)

顯然,后者是算法的主要步驟.這樣,經(jīng)典貝葉斯分類算法所需的時(shí)間復(fù)雜度為O(NM2+M2).因此,如何高效地執(zhí)行該步驟,是提高整個(gè)算法效率的關(guān)鍵.在第2節(jié)中,本文為該步驟設(shè)計(jì)了相應(yīng)的量子算法.與經(jīng)典貝葉斯二元分類算法相比,該量子算法能夠指數(shù)級地降低時(shí)間復(fù)雜度.

1.2 量子計(jì)數(shù)

(5)

(6)

進(jìn)一步,對G算子進(jìn)行相位估計(jì)可得整個(gè)系統(tǒng)空間量子態(tài)為:

(7)

然后,在計(jì)算機(jī)上對寄存器|2θ〉進(jìn)行測量,可以獲得θ的估計(jì)值,從而得到問題的解的個(gè)數(shù)D.

2 基于量子計(jì)數(shù)的貝葉斯二元分類算法

本節(jié)所提出的量子貝葉斯二元分類算法,主要分為4個(gè)步驟:制備量子初態(tài);量子計(jì)數(shù);量子測量得到相關(guān)概率;通過后續(xù)簡單的計(jì)算,確定測試樣本的類別.整個(gè)量子算法電路圖如圖1所示.

圖1 量子貝葉斯二元分類算法的整體量子電路圖Fig.1 The overall quantum circuit diagram of quantum Bayesian binary classification algorithm

步驟1:制備量子初態(tài)

考慮M維向量,將該經(jīng)典數(shù)據(jù)映射到量子態(tài),需要log2M個(gè)量子比特來存儲(chǔ)該數(shù)據(jù).這里,利用量子隨機(jī)訪問存儲(chǔ)器[16](quantum random access memory,QRAM)來并行訪問數(shù)據(jù),并以相干量子疊加方式進(jìn)行內(nèi)存訪問.假設(shè)R是一個(gè)地址寄存器,它包含疊加的地址(為疊加地址的振幅),QRAM將返回1個(gè)屬于該地址寄存器的疊加量子態(tài).如式(8)所示:

∑αφα|α〉R→∑αφα|α〉R|Dα〉dr.

(8)

本算法需要O(logMN)次操作來訪問數(shù)據(jù),N為訓(xùn)練數(shù)據(jù)樣本數(shù),如式(9)、(10)所示:

(9)

(10)

步驟2:量子計(jì)數(shù)

圖2 量子黑盒電路圖Fig.2 The quantum oracle circuit diagram

(11)

此時(shí),便實(shí)現(xiàn)了類似于Grover的黑盒操作.

(12)

構(gòu)造與之對應(yīng)的Gkj算子,

Gkj=(2|χN〉〈χN|-IN)O,

(13)

那么,在Gkj算子的本征態(tài)空間上重新描述|ψ〉,可得:

(14)

然后借助輔助粒子進(jìn)行相位估計(jì)[3],可得:

(15)

步驟3:投影測量

步驟4:計(jì)算類別

3 復(fù)雜度分析

這一節(jié)中,對上述量子算法的時(shí)間復(fù)雜度進(jìn)行簡要分析.各步驟的時(shí)間復(fù)雜度如表1所示.

表1 復(fù)雜度分析Table 1 The complexity analysis

4 結(jié)論