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

陸春悅,郭躬德,林 崧

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

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

1 背景知識

1.1 樸素貝葉斯分類算法

(1)

(2)

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

(3)

(4)

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

1.2 量子計數(shù)

(5)

(6)

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

(7)

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

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

本節(jié)所提出的量子貝葉斯二元分類算法,主要分為4個步驟:制備量子初態(tài);量子計數(shù);量子測量得到相關(guān)概率;通過后續(xù)簡單的計算,確定測試樣本的類別.整個量子算法電路圖如圖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個量子比特來存儲該數(shù)據(jù).這里,利用量子隨機訪問存儲器[16](quantum random access memory,QRAM)來并行訪問數(shù)據(jù),并以相干量子疊加方式進行內(nèi)存訪問.假設(shè)R是一個地址寄存器,它包含疊加的地址(為疊加地址的振幅),QRAM將返回1個屬于該地址寄存器的疊加量子態(tài).如式(8)所示:

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

(8)

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

(9)

(10)

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

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

(11)

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

(12)

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

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

(13)

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

(14)

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

(15)

步驟3:投影測量

步驟4:計算類別

3 復雜度分析

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

表1 復雜度分析Table 1 The complexity analysis

4 結(jié)論