Quantum recommendation algorithm based on Hamming distance

doi:10.3969/j.issn.1007-5461.2021.03.009

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

CLC Number:

TP319

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

References 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.