基于汉明距离的量子推荐算法

doi:10.3969/j.issn.1007-5461.2021.03.009

量子电子学报 ›› 2021, Vol. 38 ›› Issue (3): 332-340.doi: 10.3969/j.issn.1007-5461.2021.03.009

基于汉明距离的量子推荐算法

陈梦涵, 郭躬德, 林崧∗

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

收稿日期:2021-01-04 修回日期:2021-03-17 出版日期:2021-05-28 发布日期:2021-05-28
通讯作者: E-mail: lins95@fjnu.edu.cn
作者简介:陈梦涵( 1997 - ), 女, 安徽人, 研究生, 主要从事量子机器学习方面的研究。E-mail: 1446514387@qq.com
基金资助:
Supported by National Natural Science Foundation of China (国家自然科学基金, 61772134, 61976053), Program for New Century Excellent Talents in Fujian Province University (福建省高等学校新世纪优秀人才支持计划), Natural Science Foundation of Fujian Province of China (福建省自然科学基金, 2018J01776)

Quantum recommendation algorithm based on Hamming distance

CHEN Menghan, GUO Gongde, LIN Song∗

School of Mathematics and Informatics, Fujian Normal University, Fuzhou 350007, China

Received:2021-01-04 Revised:2021-03-17 Published:2021-05-28 Online:2021-05-28

摘要/Abstract

摘要： 利用量子汉明距离提出一个基于内容的量子推荐算法。该算法利用量子力学特性对用户观看的历史电影属性并行求和, 从而有效计算出用户的偏好属性, 然后基于汉明距离得到新电影属性与其偏好属性的相似度, 并快速查找到相似度高的新电影, 完成推荐任务。分析表明所提出算法与经典算法相比在运行时间上有指数级加速。

Abstract: A content-based quantum recommendation algorithm based on quantum Hamming distance is proposed. In the proposed algorithm, quantum mechanical properties are utilized to sum up the attributes of historical movies watched by users parallelly, so that the favorite attributes of the users can be calculated efficiently. Then, the quantum Hamming distance between the new movies’ attributes and the favorite attributes is derived, which represents the similarity of them. Finally, one new movie with the highest similarity is obtained, which means the task of recommendation is achieved. Analysis shows that the proposed algorithm is exponentially faster in the runtime than the classical counterpart.

Key words: quantum information, quantum recommendation algorithm, quantum Hamming distance; quantum parallelism, amplitude amplification

中图分类号:

TP319

陈梦涵, 郭躬德, 林崧∗. 基于汉明距离的量子推荐算法[J]. 量子电子学报, 2021, 38(3): 332-340.

CHEN Menghan, GUO Gongde, LIN Song∗. Quantum recommendation algorithm based on Hamming distance[J]. Chinese Journal of Quantum Electronics, 2021, 38(3): 332-340.

参考文献 32

[1]	Schuld M, Sinayskiy I, Petruccione F. An introduction to quantum machine learning [J]. Contemporary Physics, 2015, 56(2):
17	2-185.
[2]	Dunjko V, Briegel H J. Machine learning & artificial intelligence in the quantum domain: A review of recent progress [J].
	Reports on Progress in Physics, 2018, 81(7): 074001.
[3]	Dai J, Li Z Q, Pan S H, et al. Deutsch-Jozsa algorithm realization based on IBM Q [J]. Chinese Journal of Quantum Electronics,
20	20, 37(2): 202-209.
	戴娟, 李志强, 潘苏含, 等. 基于IBM Q 的Deutsch-Jozsa 算法实现[J]. 量子电子学报, 2020, 37(2): 202-209.
[4]	Motta M, Sun C, Tan A T K, et al. Determining eigenstates and thermal states on a quantum computer using quantum imaginary
	time evolution [J]. Nature Physics, 2020, 16(2): 205-210.
[5]	Cao D. Cluster states quantum fuzzy hashing and covert information search [J]. Chinese Journal of Quantum Electronics, 2015,
32	(1): 58-68.
[6]	Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM
	Review, 1999, 41(2): 303-332.
[7]	Grover L K. Quantum mechanics helps in serching for a needle in a haystack [J]. Physical Review Letters, 1997, 79(2): 325-328.
[8]	Biamonte J, Wittek P, Pancotti N, et al. Quantum machine learning [J]. Nature, 2017, 549(7671): 195-202.
[9]	Liu N N, Rebentrost P. Quantum machine learning for quantum anomaly detection [J]. Physical Review A, 2018, 97(4): 042315.
[10]	Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations [J]. Physical Review Letters, 2009,
10	3(15): 150502.
[11]	Wossnig L, Zhao Z K, Prakash A. A quantum linear system algorithm for dense matrices [J]. Physical Review Letters, 2017,
12	0(5): 050502.
[12]	Wang G M. Quantum algorithm for linear regression [J]. Physical Review A, 2017, 96(1): 012335.
[13]	Zhang D B, Xue Z Y, Zhu S L, et al. Realizing quantum linear regression with auxiliary qumodes [J]. Physical Review A, 2019,
99	(1): 012331.
[14]	Lin J, Bao W S, Zhang S, et al. An improved quantum principal component analysis algorithm based on the quantum singular
	threshold method [J]. Physics Letters A, 2019, 383(24): 2862-2868.
[15]	Fan D C, Song Z L, Jon S, et al. An improved quantum clustering algorithm with weighted distance based on PSO and research
	on the prediction of electrical power demand [J]. Journal of Intelligent & Fuzzy Systems, 2020, 38(2): 2359-2367.
[16]	Guo G D, Yu K,Wang H, et al. Quantum hierarchical agglomerative clustering based on one dimension discrete quantum walk
	with single-point phase defects [J]. Computers, Materials & Continua, 2020, 65(2): 1397-1409.
[17]	Yu K, Guo G D, Li J, et al. Quantum algorithms for similarity measurement based on Euclidean distance [J]. International
	Journal of Theoretical Physics, 2020, 59(10): 3134-3144.
[18]	Xu Y Z, Guo G D, Cai B B, et al. Quantum clustering algorithm based on one-dimensional three-state quantum walk [J].
	Computer Science, 2016, 43(3): 80-83.
	徐永振, 郭躬德, 蔡彬彬, 等. 基于一维三态量子游走的量子聚类算法[J]. 计算机科学, 2016, 43(3): 80-83.
[19]	Chen S L, Huang C H. Construction of continuous-variable coherent state quantum neural network model [J]. Chinese Journal
	of Quantum Electronics, 2017, 34(4): 467-472.
	陈珊琳, 黄春晖. 连续变量相干态量子神经网络模型的构建[J]. 量子电子学报, 2017, 34(4): 467-472.
[20]	Cong I, Choi S, Lukin M D. Quantum convolutional neural networks [J]. Nature Physics, 2019, 15(12): 1273-1278.
[21]	Chen Y, Li X, Liu J, et al. Recommendation system for adaptive learning [J]. Applied Psychological Measurement, 2018, 42(1):
24	-41.
[22]	Wei J, He J, Chen K, et al. Collaborative filtering and deep learning based recommendation system for cold start items [J].
	Expert Systems With Applications, 2017, 69(9): 29-39.
[23]	Tarus J K, Niu Z D, Mustafa G M, et al. Knowledge-based recommendation: A review of ontology-based recommender
	systems for e-learning [J]. Artificial Intelligence Review, 2018, 50(1): 21-48.
[24]	Sawerwain M, Wr´oblewski M. Recommendation systems with the quantum k-NN and Grover algorithms for data processing
[J]	International Journal of Applied Mathematics and Computer Science, 2019, 29(1): 139-150.
[25]	Ruan Y, Xue X L, Liu H, et al. Quantum algorithm for K-nearest neighbors classification based on the metric of Hamming
	distance [J]. International Journal of Theoretical Physics, 2017, 56(11): 3496-3507.
[26]	Linke N M, Maslov D, Roetteler M, et al. Experimental comparison of two quantum computing architectures [J]. PNAS, 2017,
11	4(13): 3305-3310.
[27]	Zulehner A, Paler A, Wille R, et al. An efficient methodology for mapping quantum circuits to the IBM QX architectures [J].
	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(7): 1226-1236.
[28]	Kaye P. Reversible addition circuit using one ancillary bit with application to quantum computing [J]. arXiv: quant-ph/0408173,
	2004.
[29]	Bang J, Dutta A, Lee S, et al. Optimal usage of quantum random access memory in quantum machine learning [J]. Physical
	Review A, 2019, 99(1): 012326.
[30]	Brassard G, Hoyer P, Mosca M. Quantum amplitude amplification and estimation [J]. arXiv: quant-ph/0005055, 2000.
[31]	Rastegin A E. On the role of dealing with quantum coherence in amplitude amplification [J]. Quantum Information Processing,
20	18, 17(7): 179-194.
[32]	Yu C H, Gao F,Wang Q L, et al. Quantum algorithm for association rules mining [J]. Physical Review A, 2016, 94(4): 042311.

基于汉明距离的量子推荐算法

Quantum recommendation algorithm based on Hamming distance

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 32

相关文章 15

编辑推荐

Metrics

本文评价

[1]	孔令航, 陈建鑫 . 扩展量子门集在量子纠错中的应用(特邀,封面文章)[J]. 量子电子学报, 2026, 43(4): 513-523.
[2]	刘潺, 黄磊, 王铮, 朱凌瑾 . 基于 KNN 的连续变量量子密钥分发实际攻击检测[J]. 量子电子学报, 2025, 42(6): 818-828.
[3]	郝鹏磊, 韩正甫, . 量子光源的相位随机化检测装置[J]. 量子电子学报, 2025, 42(5): 686-693.
[4]	卢晓同, 常宏, . 基于光晶格原子钟的量子精密测量 (特邀, 封面文章）[J]. 量子电子学报, 2025, 42(4): 437-449.
[5]	牛素俭解孟雨周志远史保森. 基于量子纠缠光源的椭圆偏振测量技术研究进展 (特邀)[J]. 量子电子学报, 2025, 42(4): 450-463.
[6]	杨玉, 张沛, 李福利, . 反馈控制增强的量子多参数估计研究 (特邀)[J]. 量子电子学报, 2025, 42(4): 464-475.
[7]	陆茂霖, 白妙青, 秦成兵, . 基于单光子探测器阵列的抗噪声频域成像研究 (特邀)[J]. 量子电子学报, 2025, 42(4): 537-545.
[8]	韩顺利, 刘贵祥, 柴继旺, 张映昀, 柳扬. 基于里德堡原子的超外差宽带频谱测量设计与实现 (特邀)[J]. 量子电子学报, 2025, 42(4): 546-555.
[9]	袁昊, 罗兵, 陈建君, 陈震, 杨文广, 张好, 张临杰, 张豪峰 . 基于里德堡原子的电晕放电信号测量 (特邀)[J]. 量子电子学报, 2025, 42(4): 556-564.
[10]	杜艺杰, 吕子瑶, 胡伟东, 何军, 刘志慧, 董涛, 金世超. 基于原子天线的低频电场量子精密测量和应用[J]. 量子电子学报, 2024, 41(5): 701-712.
[11]	施锡平, 刘尉悦. 线性光学采样算法中的多普勒补偿研究[J]. 量子电子学报, 2024, 41(5): 729-737.
[12]	刘学铭 , 陈永聪 , 敖平. 热噪声环境下的量子调控优化[J]. 量子电子学报, 2024, 41(1): 103-112.
[13]	杨涵 , 冯雁 , 谢四江 , . 基于半量子安全直接通信的量子拍卖协议[J]. 量子电子学报, 2024, 41(1): 125-134.
[14]	杨冬晗 , 李志强, 吴希 , 潘文杰 , 杨辉. 基于最小权和模板匹配的Oracle线路优化[J]. 量子电子学报, 2024, 41(1): 151-160.
[15]	牛义仁 , 管致锦 , 李海峰 , 陆俊宇. 一种提高量子线路保真度的转换方法[J]. 量子电子学报, 2024, 41(1): 161-169.