陳夢涵,郭躬德,林崧

(福建師范大學(xué)數(shù)學(xué)與信息學(xué)院,福建 福州 350007)

0 引言

隨著全球存儲的數(shù)據(jù)量以約20%的速度增長[1],探尋高效機(jī)器學(xué)習(xí)方法的壓力也日益增加。毋庸置疑,量子計(jì)算[2?5]在時(shí)間復(fù)雜度上展現(xiàn)的巨大優(yōu)勢正在進(jìn)一步解決這個(gè)問題。例如,1994年Shor[6]提出著名的量子分解Shor算法,證明可在多項(xiàng)式時(shí)間內(nèi)完成大數(shù)因子分解;隨后Lov[7]于1996年利用幅度放大技術(shù)設(shè)計(jì)了一種量子搜索算法,相較于傳統(tǒng)的搜索算法,實(shí)現(xiàn)了二次加速。在上述背景下,量子計(jì)算相比于經(jīng)典計(jì)算在解決特定問題上所具備的速度優(yōu)勢,使得越來越多的學(xué)者探究如何利用量子計(jì)算更高效地解決機(jī)器學(xué)習(xí)問題。近年來,人們充分利用量子力學(xué)特性設(shè)計(jì)了一些巧妙的量子機(jī)器學(xué)習(xí)算法[8,9],如量子線性方程組求解[10,11]、量子線性回歸[12,13]、量子主成分分析[14]、量子聚類[15?18]、量子神經(jīng)網(wǎng)絡(luò)[19,20]等。

推薦算法[21?23]是一類常見的機(jī)器學(xué)習(xí)算法,其利用用戶過去的樣本數(shù)據(jù)計(jì)算出用戶的偏好,并由此推測出用戶可能喜歡的物品。推薦算法中最常見的一個(gè)例子就是電影推薦算法,此算法通過用戶過去觀看的電影,預(yù)測出用戶下一次最有可能觀看的電影,從而針對用戶做出較準(zhǔn)確的推薦。然而,隨著“大數(shù)據(jù)”時(shí)代的到來,數(shù)據(jù)規(guī)模越來越龐大,經(jīng)典計(jì)算并不能很好地解決高計(jì)算成本的問題。量子并行計(jì)算為該問題提供了一個(gè)有效的解決途徑。2018年,Sawerwain和Wr′oblewski[24]提出一種基于量子最近鄰的量子推薦算法,此算法用量子最近鄰法[25]對推薦的元素進(jìn)行分類,之后用Grover搜索算法來提高推薦的可能性。該量子推薦算法以用戶的年齡、職業(yè)、評分等作為用戶屬性,并結(jié)合新電影屬性生成相似度較高的推薦。然而,該算法存在一些局限性。例如,職業(yè)、年齡屬于個(gè)人隱私,且評分具有較強(qiáng)的主觀性。針對這一問題,本文提出一個(gè)基于內(nèi)容的量子推薦算法,該算法基于漢明距離對用戶過去看過的電影進(jìn)行分析,并行計(jì)算出用戶的偏好屬性,然后將其偏好屬性與新電影屬性并行比較,高效計(jì)算其相似度,最終得到用戶可能喜歡的電影并推薦給用戶。

1 預(yù)備知識

1.1 基于內(nèi)容的經(jīng)典推薦算法

基于內(nèi)容的推薦算法是目前應(yīng)用最為廣泛的一種推薦機(jī)制。它是根據(jù)推薦物品或內(nèi)容的樣本數(shù)據(jù),發(fā)現(xiàn)物品或內(nèi)容的相關(guān)性,再基于用戶以往的喜好記錄,推薦給用戶相似的物品。例如,用戶看了哈利波特I,此推薦算法發(fā)現(xiàn)哈利波特II-VI與哈利波特I在內(nèi)容方面(關(guān)鍵詞)相似度很高,因此把后者推薦給該用戶。

如表1所示,電影數(shù)據(jù)庫為例來分析該類算法的運(yùn)行機(jī)制。對于每一位用戶,電影數(shù)據(jù)庫中包含已觀看的N部電影,電影的屬性共有M種。因此,可用一個(gè)M×N的二進(jìn)制矩陣表示上述內(nèi)容,即

表 1電影數(shù)據(jù)庫Table 1 Database of the movies

經(jīng)典推薦算法大致步驟描述如下:

步驟C2:對于每種屬性的次數(shù)yi,將其與一個(gè)閾值t進(jìn)行比較,即計(jì)算yi與t的大小,若yi≥t,則該屬性i是用戶喜歡的屬性,否則為不感興趣的屬性;

步驟C3:對于新的電影,根據(jù)新電影屬性與用戶偏好屬性的相似度進(jìn)行個(gè)性化推薦,即計(jì)算新電影屬性與用戶喜歡的屬性的漢明距離,若該距離大于某個(gè)閾值則將電影推薦給該用戶。

1.2 量子計(jì)算的基礎(chǔ)知識

經(jīng)典計(jì)算機(jī)通過操作經(jīng)典比特0和1進(jìn)行運(yùn)算,類似地,量子計(jì)算機(jī)[26,27]操縱量子比特|0〉和|1〉。比特和量子比特之間的區(qū)別在于量子比特可以組成疊加態(tài),如

式中α和β是復(fù)數(shù),且α2+β2=1。盡管很多時(shí)候把它們當(dāng)做實(shí)數(shù)也沒有問題。換句話說,量子比特的狀態(tài)是二維復(fù)向量空間中的向量。

量子邏輯門是作用于單個(gè)或者多個(gè)量子比特以實(shí)現(xiàn)某個(gè)計(jì)算功能的酉操作。最簡單的是對單量子進(jìn)行操作的邏輯門,常見的為Hadamard門和Pauli門操作,其Hadamard矩陣、Pauli-X矩陣、Pauli-Y矩陣和Pauli-Z矩陣可分別表示為

常見的還有對雙量子進(jìn)行操作的邏輯門,一般有受控非門CNOT和受控交換門SWAP,相應(yīng)矩陣可分別表示為

利用以上量子基礎(chǔ)知識可實(shí)現(xiàn)一個(gè)簡單的量子加法操作[28],如圖1(a)所示。即一個(gè)二進(jìn)制數(shù)(b=b0b1···bn?1)遞增時(shí),該電路先翻轉(zhuǎn)最后一位(bn?1)。若從0翻轉(zhuǎn)到1,則結(jié)束整個(gè)操作;若從1翻轉(zhuǎn)到0,則繼續(xù)翻轉(zhuǎn)前一位(bn?2),直到將一個(gè)量子比特從0翻轉(zhuǎn)到1,則完成加法操作。線路中最后一位輔助位是一個(gè)“標(biāo)志”,會在第一次將某一位從0翻轉(zhuǎn)到1時(shí)發(fā)出停止信號。例如,當(dāng)|a〉為|0〉時(shí),|b〉則不進(jìn)行操作,即實(shí)現(xiàn)了|b+a〉;當(dāng)|a〉為|1〉時(shí),假設(shè)|b〉為|5〉,則其二進(jìn)制表示為|101〉。基于上面的描述可知:首先翻轉(zhuǎn)最后一位,從|1〉翻轉(zhuǎn)到|0〉;接下來,翻轉(zhuǎn)第二位,從|0〉翻轉(zhuǎn)到|1〉。此時(shí)結(jié)束整個(gè)操作,且二進(jìn)制表示變?yōu)閨110〉,即實(shí)現(xiàn)了|5+1〉=|6〉。圖1(b)是圖1(a)的概括圖,后續(xù)將用inCn門來表示上述量子加法操作。

圖1 (a)b+1的線路圖;(b)b+1的概括圖Fig.1 (a)A circuit implementing for b+1;(b)Summary figure for b+1

2 量子推薦算法

2.1 量子推薦算法的實(shí)現(xiàn)

與經(jīng)典推薦算法相同,假設(shè)用戶看過N部電影,電影的所有屬性是M種,數(shù)據(jù)(yij)M×N存儲在量子隨機(jī)存儲器(QRAM)[29]中。算法的首要任務(wù)是從Oracle中讀取矩陣(yij)M×N的值;然后計(jì)算每種屬性出現(xiàn)的電影次數(shù),以此得出用戶的偏好屬性;最后根據(jù)用戶偏好屬性及新電影屬性的相似程度進(jìn)行個(gè)性化推薦。算法具體步驟描述如下:

步驟Q1:制備量子推薦算法所需的量子初態(tài)。

在當(dāng)前量子態(tài)中加入一個(gè)包含N位量子比特的第4量子寄存器,使得系統(tǒng)的狀態(tài)為

圖2 |j〉和|yij〉控制附加量子比特來獲得|yij〉相對應(yīng)的直積態(tài)Fig.2 The qubits|j〉and|yij〉control auxiliary qubits to obtain corresponding direct product

步驟Q2:計(jì)算每種屬性出現(xiàn)的電影次數(shù)。

步驟Q3:計(jì)算用戶的偏好屬性。

圖 3 計(jì)算的線路圖Fig.3 A circuit implementing

步驟Q4:讀取新電影的屬性值。

現(xiàn)根據(jù)第0個(gè)和第1個(gè)寄存器,從Oracle中讀取第g部新電影中的第i種屬性值|xgi〉7,則系統(tǒng)中的狀態(tài)為

步驟Q5:制備算法所需的直積態(tài)。

圖4 (a)計(jì)算閾值t的補(bǔ)碼操作;(b)計(jì)算|di〉與|φ〉的和的線路圖Fig.4 (a)Operation for computing complement of threshold value t;(b)A circuit for implementing sum of|di〉and|φ〉

步驟Q6:計(jì)算新電影屬性與用戶偏好屬性的相似度。

步驟Q7:判斷相似度高低。

設(shè)置一個(gè)閾值v,將漢明距離hg與v相減,得到zg。由步驟Q3的分析,易知當(dāng)zg為|0〉時(shí),意味此部電影含有較多的用戶偏好屬性,則用戶可能會喜歡該部電影。其操作與步驟Q3相同,線路圖類似于圖4。當(dāng)前的系統(tǒng)狀態(tài)為

圖5 |si0〉與|xgi〉分別是|0〉和|1〉時(shí),執(zhí)行受控非門的線路圖Fig.5 Performing controlled-NOT operation when the|si0〉and|xgi〉are|0〉and|1〉,respectively

步驟Q8:執(zhí)行測量操作。

2.2 算法時(shí)間復(fù)雜度分析

3 結(jié)論

提出一個(gè)基于內(nèi)容的量子推薦算法,該算法首先利用漢明距離計(jì)算出用戶的偏好屬性,之后并行計(jì)算其偏好屬性與新樣本數(shù)據(jù)的相似度,最后將相似度高的樣本推薦給用戶。為了完成這個(gè)任務(wù),所提出算法利用量子加法實(shí)現(xiàn)高效計(jì)算量子漢明距離以及距離與閾值之間的大小。在獲取所需的直積態(tài)方面,僅需要執(zhí)行一次黑盒操作,相較于文獻(xiàn)[32]中需要O(N)個(gè)黑盒操作,所提方法更易實(shí)現(xiàn)且復(fù)雜度也更低。所提出的量子推薦算法通過訓(xùn)練樣本數(shù)據(jù)集計(jì)算出用戶的偏好屬性,無需提供一些隱私信息和主觀性數(shù)據(jù),克服了已有量子推薦算法[23]的局限性。此外,對算法的時(shí)間復(fù)雜度進(jìn)行了簡要分析,結(jié)果表明與經(jīng)典推薦算法相比,此算法有指數(shù)級的時(shí)間優(yōu)化。值得一提的是,所提出量子推薦算法是一個(gè)基礎(chǔ)算法,對算法的每一步驟都給出了詳細(xì)的量子線路圖。因此,本算法可用來構(gòu)建復(fù)雜的量子機(jī)器學(xué)習(xí)算法。