陈梦涵,郭躬德,林崧

(福建师范大学数学与信息学院,福建 福州 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搜索算法来提高推荐的可能性。……