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

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]	贾玮 , 张强强 , 卞宇翔 , 李威 . E91-QKD 中集体攻击上限的研究[J]. 量子电子学报, 2023, 40(3): 407-414.
[2]	曹睿 , 袁晨智 , 沈思 , 张子昌 , 范云茹 , 李加睿 , 李浩 , 尤立星 , 周强 , 王子竹∗. 三维时间片最大纠缠态的最优检测[J]. 量子电子学报, 2023, 40(1): 85-94.
[3]	赵良圆曹凌云梁洪源韦峥伍千军钱建林韩正甫. 基于不同光纤的波分复用型量子密钥分配研究[J]. 量子电子学报, 2022, 39(5): 776-785.
[4]	吴希, 李志强∗. 基于 Cirq 的Grover 搜索算法的电路实现[J]. 量子电子学报, 2022, 39(3): 431-438.
[5]	戴娟∗, 李志强, 杨冬晗. 基于 Cirq 的Deutsch-Jozsa 电路综合算法[J]. 量子电子学报, 2022, 39(3): 439-445.
[6]	徐凯♯, 曹洹, ♯, 张超∗, 胡晓敏, 黄运锋∗, 柳必恒, 李传锋∗. 光子轨道角动量量子态传输研究进展[J]. 量子电子学报, 2022, 39(1): 3-31.
[7]	王纺翔, 陈巍, ∗. 综述: 基于轨道角动量光子态的高维量子密钥分发[J]. 量子电子学报, 2022, 39(1): 64-80.
[8]	茹世浩, 王啸, 王云龙, 王斐然, 刘瑞丰, 张沛, 李福利, ∗. 光子轨道角动量的量子操控与应用[J]. 量子电子学报, 2022, 39(1): 96-109.
[9]	常泓吴怡婷林崧. 基于 Bell 态的量子安全多方求和[J]. 量子电子学报, 2021, 38(6): 830-837.
[10]	唐世彪∗, 程节, 栗帅. 量子密钥分发产品随机数芯片阵列方案研究[J]. 量子电子学报, 2021, 38(4): 468-476.
[11]	范宇腾, 索磊 , 张春辉, 陈家明, 王琴, ∗. 基于线性光学元件的被动式诱骗态量子数字签名方案[J]. 量子电子学报, 2021, 38(4): 485-495.
[12]	虞味周媛媛周学军. 基于弱相干态光源的相位匹配诱骗态量子密钥分配方案[J]. 量子电子学报, 2021, 38(1): 37-44.
[13]	郭梦琪, 巩龙延∗. I_{3322}不等式的量子违背研究[J]. 量子电子学报, 2021, 38(1): 50-56.
[14]	唐世彪∗, 程节, 栗帅. 高速QKD系统的随机数源及实时自检方案研究[J]. 量子电子学报, 2021, 38(1): 86-93.
[15]	朱孟正, 赵春然, 公丕锋, 叶柳. 基于坐标系旋转实现对实数态克隆的优化[J]. 量子电子学报, 2020, 37(3): 337-341.