Quantum Nearest Neighbor Collaborative Filtering Algorithm for Recommendation System
Authors: 
Jiaye Li, Jinjing Shi, Jian Zhang, Yuhu Lu, Qin Li, Chunlin Yu, 
Shichao ZhangAuthors Info & Claims
Article No.: 201, Pages 1 - 28
Abstract
Recommendation has become especially crucial during the COVID-19 pandemic as a significant number of people rely on online shopping from home. Existing recommendation algorithms, designed to address issues like cold start and data sparsity, often overlook the time constraints of users. Specifically, users expect to receive recommendations for products of interest in the shortest possible time. To address this challenge, we propose a novel collaborative filtering recommendation algorithm that leverages the advantages of quantum computing circuits based on data reconstruction. This approach allows for the rapid identification of users similar to the target user, thereby improving recommendation speed. In our method, we utilize the information of known users to linearly reconstruct that of the target users, forming a relational matrix. Subsequently, we employ \(l_{2,1}-\)norm and \(l_{1}-\)norm to sparsely constrain the relationship matrix, deducing the weight of each known user. The final step involves providing similar recommendations to target users based on these weights. Furthermore, we implement the proposed algorithm using a quantum circuit, enabling exponential acceleration. The final weight matrix is derived from the quantum state outputted by the circuit. The speed of this process is theoretically demonstrated in detail. Experimental results indicate that our algorithm outperforms state-of-the-art methods in terms of root mean squared error (RMSE), mean absolute error (MAE) and normalized discounted cumulative gain (NDCG). Compared to state-of-the-art comparison algorithms, the proposed algorithm achieves the fastest recommendation speed across eight public datasets.
References
[1]
Malak Al-Hassan, Bilal Abu-Salih, Esra’ Alshdaifat, Ahmad Aloqaily, and Ali Rodan. 2024. An improved fusion-based semantic similarity measure for effective collaborative filtering recommendations. International Journal of Computational Intelligence Systems 17, 1 (2024), 1–18.
[2]
Jinfang Sheng, Qingqing Liu, Zhengang Hou, and Bin Wang. 2023. A collaborative filtering recommendation algorithm based on community detection and graph neural network. Neural Processing Letters 55, 6 (2023), 7095–7112.
[3]
Fatemeh Rezaimehr and Chitra Dadkhah. 2023. T & TRS: Robust collaborative filtering recommender systems against attacks. Multimedia Tools and Applications 83, 11 (2023), 31701–31731.
[4]
Nawaf Alharbe, Mohamed Ali Rakrouki, and Abeer Aljohani. 2023. A collaborative filtering recommendation algorithm based on embedding representation. Expert Systems with Applications 215 (2023), 119380.
[5]
Jinjing Shi, Yongze Tang, Yuhu Lu, Yanyan Feng, Ronghua Shi, and Shichao Zhang. 2021. Quantum circuit learning with parameterized boson sampling. IEEE Transactions on Knowledge and Data Engineering 35, 2 (2021), 1965–1976.
[6]
Jiaye Li, Jian Zhang, Jilian Zhang, and Shichao Zhang. 2023. Quantum KNN classification with k value selection and neighbor selection. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43, 5 (2023), 1332–1345.
[7]
Chao-Hua Yu, Fei Gao, and Qiao-Yan Wen. 2017. Quantum algorithms for ridge regression. In IEEE Transactions on Knowledge and Data Engineering, 33, 3 (March 2021), 858–866. DOI:
[8]
Chao-Hua Yu, Fei Gao, Chenghuan Liu, Du Huynh, Mark Reynolds, and Jingbo Wang. 2019. Quantum algorithm for visual tracking. Physical Review A 99, 2 (2019), 022301.
[9]
Xiaofeng Zhu, Shichao Zhang, Wei He, Rongyao Hu, Cong Lei, and Pengfei Zhu. 2018. One-step multi-view spectral clustering. IEEE Transactions on Knowledge and Data Engineering 31, 10 (2018), 2022–2034.
[10]
Sanjaya Kumar Panda, Sourav Kumar Bhoi, and Munesh Singh. 2020. A collaborative filtering recommendation algorithm based on normalization approach. Journal of Ambient Intelligence and Humanized Computing 11 (2020), 4643–4665.
[11]
Man Li, Luosheng Wen, and Feiyu Chen. 2021. A novel collaborative filtering recommendation approach based on soft co-clustering. Physica A: Statistical Mechanics and its Applications 561 (2021), 125140.
[12]
Jianrui Chen, Chunxia Zhao, Uliji, Lifang Chen. 2020. Collaborative filtering recommendation algorithm based on user correlation and evolutionary clustering. Complex & Intelligent Systems 6, 1 (2020), 147–156.
[13]
Ruiyang Wang and Tao Li. 2021. Collaborative filtering recommendation algorithm based on user behavior and drug semantics. Journal of Physics: Conference Series 1802 (2021), 032005.
[14]
Lili Wu. 2021. Collaborative filtering recommendation algorithm for MOOC resources based on deep learning. Complexity 2021, 1 (2021), 5555226.
[15]
Kai Zheng, Xianjun Yang, Yilei Wang, Yingjie Wu, and Xianghan Zheng. 2020. Collaborative filtering recommendation algorithm based on variational inference. International Journal of Crowd Science 4, 1 (2020), 31–44.
[16]
Fan Wang, Haibin Zhu, Gautam Srivastava, Shancang Li, Mohammad R. Khosravi, and Lianyong Qi. 2021. Robust collaborative filtering recommendation with user-item-trust records. IEEE Transactions on Computational Social Systems 9, 4 (2021), 986–996.
[17]
Chunyong Yin, Lingfeng Shi, Ruxia Sun, and Jin Wang. 2020. Improved collaborative filtering recommendation algorithm based on differential privacy protection. The Journal of Supercomputing 76, 7 (2020), 5161–5174.
[18]
Honggang Wang and Weina Fu. 2021. Personalized learning resource recommendation method based on dynamic collaborative filtering. Mobile Networks and Applications 26, 1 (2021), 473–487.
[19]
Hailong Chen, Wuyue Yan, Haijiao Sun, and Miao Cheng. 2020. Tag-extended collaborative filtering recommendation algorithm. SN Computer Science 1, 5 (2020), 1–13.
[20]
Chao Guo, Yanzhao Ren, Jingdun Jia, Sha Tao, Xinliang Liu, Wanlin Gao, and Limin Yu. 2021. A content-based recommendation algorithm for agricultural science popularization. In Proceedings of the IEEE 5th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC ’21), Vol. 5, IEEE, 136–142.
[21]
Jiangbo Shu, Xiaoxuan Shen, Hai Liu, Baolin Yi, and Zhaoli Zhang. 2018. A content-based recommendation algorithm for learning resources. Multimedia Systems 24, 2 (2018), 163–173.
[22]
Dhiraj Vaibhav Bagul and Sunita Barve. 2021. A novel content-based recommendation approach based on lda topic modeling for literature recommendation. In Proceedings of the 6th International Conference on Inventive Computation Technologies (ICICT ’21), IEEE, 954–961.
[23]
Penghui Cao and Dan Chang. 2020. A novel course recommendation model fusing content-based recommendation and k-means clustering for wisdom education. In Proceedings of the 9th International Conference on Logistics, Informatics and Service Sciences (LISS ’19), Springer, 789–809.
[24]
Thanh Trinh, Dingming Wu, Ruili Wang, and Joshua Zhexue Huang. 2021. An effective content-based event recommendation model. Multimedia Tools and Applications 80, 11 (2021), 16599–16618.
[25]
Vaishali S. Vairale and Samiksha Shukla. 2021. Recommendation of food items for thyroid patients using content-based KNN method. In: D. S. Jat, S. Shukla, A. Unal, D. K. Mishra (Eds.), Data Science and Security, Springer, 71–77. DOI:
[26]
Aashutosh Marathe, Maheshwari Patil, Shoeb Shaik, Snehal Waghmare, and Kalpana Metre. 2021. Recommendation System Using Content Based Visual Similarity. Technical Report, EasyChair.
[27]
Nguyen Van Dat, Pham Van Toan, and Ta Minh Thanh. 2021. Solving distribution problems in content-based recommendation system with Gaussian mixture model. Applied Intelligence 52, 2 (2021), 1602–1614.
[28]
André L. Zanon, Luan Souza, Diany Pressato, and Marcelo G. Manzato. 2020. WordRecommender: An explainable content-based algorithm based on sentiment analysis and semantic similarity. In Proceedings of the Brazilian Symposium on Multimedia and the Web, 181–184.
[29]
Jing Liu, Jinbao Song, Chen Li, Xiaoya Zhu, and Ruyi Deng. 2021. A hybrid news recommendation algorithm based on k-means clustering and collaborative filtering. Journal of Physics: Conference Series 1881 (2021), 032050.
[30]
Guoshuai Wei, Quanwang Wu, and Mengchu Zhou. 2021. A hybrid probabilistic multiobjective evolutionary algorithm for commercial recommendation systems. IEEE Transactions on Computational Social Systems 8, 3 (2021), 589–598.
[31]
Wei Chen, Zhendong Niu, Xiangyu Zhao, and Yi Li. 2014. A hybrid recommendation algorithm adapted in e-learning environments. World Wide Web 17, 2 (2014), 271–284.
[32]
Kunhui Lin, Jingjin Wang, and Meihong Wang. 2014. A hybrid recommendation algorithm based on hadoop. In Proceedings of the 2014 9th International Conference on Computer Science & Education, IEEE, 540–543.
[33]
Faryad Tahmasebi, Majid Meghdadi, Sajad Ahmadian, and Khashayar Valiallahi. 2021. A hybrid recommendation system based on profile expansion technique to alleviate cold start problem. Multimedia Tools and Applications 80, 2 (2021), 2339–2354.
[34]
Yonghong Tian, Bing Zheng, Yanfang Wang, Yue Zhang, and Qi Wu. 2019. College library personalized recommendation system based on hybrid recommendation algorithm. Procedia CIRP 83 (2019), 490–494.
[35]
Si Thin Nguyen, Hyun Young Kwak, Si Young Lee, and Gwang Yong Gim. 2021. Featured hybrid recommendation system using stochastic gradient descent. International Journal of Networked and Distributed Computing 9, 1 (2021), 25–32.
[36]
Jiameng Gao, Chunxia Zhang, Yanyan Xu, Meiqiu Luo, and Zhendong Niu. 2021. Hybrid microblog recommendation with heterogeneous features using deep neural network. Expert Systems with Applications 167 (2021), 114191.
[37]
Aoxiang Peng and Huiyong Liu. 2021. Hybrid program recommendation algorithm based on spark MLlib in big data environment. In Proceedings of the 9th International Conference on Computer Engineering and Networks, Springer, 489–498.
[38]
Yihao Zhang, Zhi Liu, and Chunyan Sang. 2021. Unifying paragraph embeddings and neural collaborative filtering for hybrid recommendation. Applied Soft Computing 106 (2021), 107345.
[39]
Lov K. Grover. 1997. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters 79, 2 (1997), 325.
[40]
Jiaye Li, Yangding Li, Jiagang Song, Jian Zhang, and Shichao Zhang. 2024. Quantum support vector machine for classifying noisy data. IEEE Transactions on Computers (2024), 1–14. DOI:
[41]
Iordanis Kerenidis and Anupam Prakash. 2016. Quantum recommendation systems. arXiv:1603.08675. Retrieved from https://doi.org/10.48550/arXiv.1603.08675
[42]
Ewin Tang. 2019. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 217–228.
[43]
Marek Sawerwain and Marek Wróblewski. 2019. Application of quantum k-NN and Grover’s algorithms for recommendation big-data system. In Information Systems Architecture and Technology: Proceedings of 39th International Conference on Information Systems Architecture and Technology – ISAT 2018. L. Borzemski, J. Świątek, Z. Wilimowska (Eds.), Advances in Intelligent Systems and Computing, Vol. 852. Springer, Cham, 235–244. DOI:
[44]
Panpan Wang, Zhao Li, Yazhou Zhang, Yuexian Hou, and Liangzhu Ge. 2019. QPIN: A quantum-inspired preference interactive network for e-commerce recommendation. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2329–2332.
[45]
Xiaoqiang Wang, Lejia Gu, Joseph Heung-wing Joseph Lee, and Guofeng Zhang. 2019. Quantum tensor singular value decomposition with applications to recommendation systems. arXiv:1910.01262. Retrieved from https://doi.org/10.48550/arXiv.1910.01262
[46]
Desislav Andreev. 2019. Quantum recommendation system for image feature matching and pattern recognition. In Proceedings of the Future Technologies Conference, Springer, 497–511.
[47]
Likhesh Kolhe, Ashok Kumar Jetawat, and Vaishali Khairnar. 2021. Robust product recommendation system using modified grey wolf optimizer and quantum inspired possibilistic fuzzy C-means. Cluster Computing 24, 2 (2021), 953–968.
[48]
Chen Menghan, Guo Gongde, and Lin Song. 2021. Quantum recommendation algorithm based on hamming distance. Chinese Journal of Quantum Electronics 38, 3 (2021), 332.
[49]
Riccardo Nembrini, Costantino Carugno, Maurizio Ferrari Dacrema, and Paolo Cremonesi. 2022. Towards recommender systems with community detection and quantum computing. In Proceedings of the 16th ACM Conference on Recommender Systems. 579–585.
[50]
Maurizio Ferrari Dacrema, Nicolo Felicioni, and Paolo Cremonesi. 2021. Optimizing the selection of recommendation carousels with quantum computing. In Proceedings of the 15th ACM Conference on Recommender Systems. 691–696.
[51]
Xiong Wang, Ruijin Wang, Dongfen Li, Daniel Adu-Gyamfi, and Yixin Zhu. 2019. QCF: Quantum collaborative filtering recommendation algorithm. International Journal of Theoretical Physics 58 (2019), 2235–2243.
[52]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Quantum random access memory. Physical Review Letters 100, 16 (2008), 160501.
[53]
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. 2018. Quantum singular-value decomposition of nonsparse low-rank matrices. Physical Review A 97, 1 (2018), 012327.
[54]
Jie Lu, Dianshuang Wu, Mingsong Mao, Wei Wang, and Guangquan Zhang. 2015. Recommender system application developments: A survey. Decision Support Systems 74 (2015), 12–32.
[55]
Jingjing Li, Mengmeng Jing, Ke Lu, Lei Zhu, Yang Yang, and Zi Huang. 2019. From zero-shot learning to cold-start recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 4189–4196.
[56]
Ziwei Zhu, Jianling Wang, and James Caverlee. 2019. Improving top-k recommendation via jointcollaborative autoencoders. In Proceedings of the World Wide Web Conference. 3483–3482.
[57]
Shang Gao and Yu-Guang Yang. 2022. A novel quantum recommender system. Physica Scripta 98, 1 (2022), 010001.
[58]
Bam Bahadur Sinha and R. Dhanalakshmi. 2022. DNN-MF: Deep neural network matrix factorization approach for filtering information in multi-criteria recommender systems. Neural Computing and Applications 34, 13 (2022), 10807–10821.
[59]
Ishaan Kumar, Yaochen Hu, and Yingxue Zhang. 2022. EFLEC: Efficient feature-leakage correction in GNN based recommendation systems. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1885–1889.
Index Terms
- Quantum Nearest Neighbor Collaborative Filtering Algorithm for Recommendation System
Recommendations
Typicality-Based Collaborative Filtering Recommendation
Collaborative filtering (CF) is an important and popular technology for recommender systems. However, current CF methods suffer from such problems as data sparsity, recommendation inaccuracy, and big-error in predictions. In this paper, we borrow ideas ...
A Collaborative Filtering Recommendation Algorithm Based on Item Classification
PACCS '09: Proceedings of the 2009 Pacific-Asia Conference on Circuits, Communications and SystemsCollaborative filtering systems represent services of personalized that aim at predicting a user’s interest on some items available in the application systems. With the development of electronic commerce, the number of users and items grows rapidly, ...
Collaborative Filtering Recommendation Algorithm Using Dynamic Similar Neighbor Probability
ADMA '09: Proceedings of the 5th International Conference on Advanced Data Mining and ApplicationsIn this paper, we focus on how to overcome several limitations in the traditional research of collaborative filtering(CF). We present a novel CF recommendation algorithm, named DSNP(Dynamic Similar Neighbor Probability). This algorithm improves the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 July 2024
Online AM: 29 June 2024
Accepted: 16 June 2024
Revised: 20 March 2024
Received: 18 May 2022
Published in TKDD Volume 18, Issue 8
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Guangxi Science and Technology
- National Natural Science Foundation of China
- Natural Science Foundation of Hunan Province
- Special Foundation for Distinguished Young Scientists of Changsha
- CCF-Baidu Open Fund
- Advanced Cryptography and System Security Key Laboratory of Sichuan Province
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 293Total Downloads
- Downloads (Last 12 months)293
- Downloads (Last 6 weeks)63
Reflects downloads up to 23 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in