陈梦涵,郭躬德,林崧

(福建师范大学数学与信息学院,福建 福州 350007)

0 引言

随着全球存储的数据量以约20%的速度增长[1],探寻高效机器学习方法的压力也日益增加。毋庸置疑,量子计算[2−5]在时间复杂度上展现的巨大优势正在进一步解决这个问题。例如,1994年Shor[6]提出著名的量子分解Shor算法,证明可在多项式时间内完成大数因子分解;随后Lov[7]于1996年利用幅度放大技术设计了一种量子搜索算法,相较于传统的搜索算法,实现了二次加速。在上述背景下,量子计算相比于经典计算在解决特定问题上所具备的速度优势,使得越来越多的学者探究如何利用量子计算更高效地解决机器学习问题。近年来,人们充分利用量子力学特性设计了一些巧妙的量子机器学习算法[8,9],如量子线性方程组求解[10,11]、量子线性回归[12,13]、量子主成分分析[14]、量子聚类[15−18]、量子神经网络[19,20]等。

推荐算法[21−23]是一类常见的机器学习算法,其利用用户过去的样本数据计算出用户的偏好,并由此推测出用户可能喜欢的物品。推荐算法中最常见的一个例子就是电影推荐算法,此算法通过用户过去观看的电影,预测出用户下一次最有可能观看的电影,从而针对用户做出较准确的推荐。然而,随着“大数据”时代的到来,数据规模越来越庞大,经典计算并不能很好地解决高计算成本的问题。量子并行计算为该问题提供了一个有效的解决途径。2018年,Sawerwain和Wr´oblewski[24]提出一种基于量子最近邻的量子推荐算法,此算法用量子最近邻法[25]对推荐的元素进行分类,之后用Grover搜索算法来提高推荐的可能性。该量子推荐算法以用户的年龄、职业、评分等作为用户属性,并结合新电影属性生成相似度较高的推荐。然而,该算法存在一些局限性。例如,职业、年龄属于个人隐私,且评分具有较强的主观性。针对这一问题,本文提出一个基于内容的量子推荐算法,该算法基于汉明距离对用户过去看过的电影进行分析,并行计算出用户的偏好属性,然后将其偏好属性与新电影属性并行比较,高效计算其相似度,最终得到用户可能喜欢的电影并推荐给用户。

1 预备知识

1.1 基于内容的经典推荐算法

基于内容的推荐算法是目前应用最为广泛的一种推荐机制。它是根据推荐物品或内容的样本数据,发现物品或内容的相关性,再基于用户以往的喜好记录,推荐给用户相似的物品。例如,用户看了哈利波特I,此推荐算法发现哈利波特II-VI与哈利波特I在内容方面(关键词)相似度很高,因此把后者推荐给该用户。

如表1所示,电影数据库为例来分析该类算法的运行机制。对于每一位用户,电影数据库中包含已观看的N部电影,电影的属性共有M种。因此,可用一个M×N的二进制矩阵表示上述内容,即

表 1电影数据库Table 1 Database of the movies

经典推荐算法大致步骤描述如下:

步骤C2:对于每种属性的次数yi,将其与一个阈值t进行比较,即计算yi与t的大小,若yi≥t,则该属性i是用户喜欢的属性,否则为不感兴趣的属性;

步骤C3:对于新的电影,根据新电影属性与用户偏好属性的相似度进行个性化推荐,即计算新电影属性与用户喜欢的属性的汉明距离,若该距离大于某个阈值则将电影推荐给该用户。

1.2 量子计算的基础知识

经典计算机通过操作经典比特0和1进行运算,类似地,量子计算机[26,27]操纵量子比特|0〉和|1〉。比特和量子比特之间的区别在于量子比特可以组成叠加态,如

式中α和β是复数,且α2+β2=1。尽管很多时候把它们当做实数也没有问题。换句话说,量子比特的状态是二维复向量空间中的向量。

量子逻辑门是作用于单个或者多个量子比特以实现某个计算功能的酉操作。最简单的是对单量子进行操作的逻辑门,常见的为Hadamard门和Pauli门操作,其Hadamard矩阵、Pauli-X矩阵、Pauli-Y矩阵和Pauli-Z矩阵可分别表示为

常见的还有对双量子进行操作的逻辑门,一般有受控非门CNOT和受控交换门SWAP,相应矩阵可分别表示为

利用以上量子基础知识可实现一个简单的量子加法操作[28],如图1(a)所示。即一个二进制数(b=b0b1···bn−1)递增时,该电路先翻转最后一位(bn−1)。若从0翻转到1,则结束整个操作;若从1翻转到0,则继续翻转前一位(bn−2),直到将一个量子比特从0翻转到1,则完成加法操作。线路中最后一位辅助位是一个“标志”,会在第一次将某一位从0翻转到1时发出停止信号。例如,当|a〉为|0〉时,|b〉则不进行操作,即实现了|b+a〉;当|a〉为|1〉时,假设|b〉为|5〉,则其二进制表示为|101〉。基于上面的描述可知:首先翻转最后一位,从|1〉翻转到|0〉;接下来,翻转第二位,从|0〉翻转到|1〉。此时结束整个操作,且二进制表示变为|110〉,即实现了|5+1〉=|6〉。图1(b)是图1(a)的概括图,后续将用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 量子推荐算法的实现

与经典推荐算法相同,假设用户看过N部电影,电影的所有属性是M种,数据(yij)M×N存储在量子随机存储器(QRAM)[29]中。算法的首要任务是从Oracle中读取矩阵(yij)M×N的值;然后计算每种属性出现的电影次数,以此得出用户的偏好属性;最后根据用户偏好属性及新电影属性的相似程度进行个性化推荐。算法具体步骤描述如下:

步骤Q1:制备量子推荐算法所需的量子初态。

在当前量子态中加入一个包含N位量子比特的第4量子寄存器,使得系统的状态为

图2 |j〉和|yij〉控制附加量子比特来获得|yij〉相对应的直积态Fig.2 The qubits|j〉and|yij〉control auxiliary qubits to obtain corresponding direct product

步骤Q2:计算每种属性出现的电影次数。

步骤Q3:计算用户的偏好属性。

图 3 计算的线路图Fig.3 A circuit implementing

步骤Q4:读取新电影的属性值。

现根据第0个和第1个寄存器,从Oracle中读取第g部新电影中的第i种属性值|xgi〉7,则系统中的状态为

步骤Q5:制备算法所需的直积态。

图4 (a)计算阈值t的补码操作;(b)计算|di〉与|φ〉的和的线路图Fig.4 (a)Operation for computing complement of threshold value t;(b)A circuit for implementing sum of|di〉and|φ〉

步骤Q6:计算新电影属性与用户偏好属性的相似度。

步骤Q7:判断相似度高低。

设置一个阈值v,将汉明距离hg与v相减,得到zg。由步骤Q3的分析,易知当zg为|0〉时,意味此部电影含有较多的用户偏好属性,则用户可能会喜欢该部电影。其操作与步骤Q3相同,线路图类似于图4。当前的系统状态为

图5 |si0〉与|xgi〉分别是|0〉和|1〉时,执行受控非门的线路图Fig.5 Performing controlled-NOT operation when the|si0〉and|xgi〉are|0〉and|1〉,respectively

步骤Q8:执行测量操作。

2.2 算法时间复杂度分析

3 结论

提出一个基于内容的量子推荐算法,该算法首先利用汉明距离计算出用户的偏好属性,之后并行计算其偏好属性与新样本数据的相似度,最后将相似度高的样本推荐给用户。为了完成这个任务,所提出算法利用量子加法实现高效计算量子汉明距离以及距离与阈值之间的大小。在获取所需的直积态方面,仅需要执行一次黑盒操作,相较于文献[32]中需要O(N)个黑盒操作,所提方法更易实现且复杂度也更低。所提出的量子推荐算法通过训练样本数据集计算出用户的偏好属性,无需提供一些隐私信息和主观性数据,克服了已有量子推荐算法[23]的局限性。此外,对算法的时间复杂度进行了简要分析,结果表明与经典推荐算法相比,此算法有指数级的时间优化。值得一提的是,所提出量子推荐算法是一个基础算法,对算法的每一步骤都给出了详细的量子线路图。因此,本算法可用来构建复杂的量子机器学习算法。