Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SPIN

Quantum-Inspired Recommendation System with Threshold Proportion Interception

Meng Qiao, Zheng Shan, Junchao Wang, Huihui Sun, Fudong Liu

Published Sep 1, 2021• 1 citation
Publisher

Abstract

Modern recommendation systems leverage historical behavior information to generate precise recommendation results for users. However, when the data scale of users and items is large, it is difficult to generate recommendation results in time. Tang proposed a quantum-inspired recommendation algorithm, which could solve the recommendation problem in constant time complexity. However, Tang’s approach is based on a set of assumptions which rely heavily on some empirical parameters. The time complexity for calculating parameters is high. Thus, this approach cannot be directly applied in industrial applications. In this paper, we propose a method, namely, Quantum-inspired Recommendation system with threshold Proportion Interception (QRPI), which is based on the quantum-inspired recommendation system and more suitable for industrial environments. Compared with the existing widely used recommendation algorithms, we show through numerical experiments that our solution can achieve almost the same performance with better efficiency.

DOI
10.1142/s2010324721400051

Related papers

Quantum-inspired algorithms in practice

Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan +1 more

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

arXiv:1905.10415•Quantum•Aug 13, 2020•134 citations

Quantum-Inspired Algorithms for Large-Scale Data Analytics: A Tensor Network Approach

Jasmin Jarsania, Chhelabhai Chavda

While full-scale quantum computers remain years away from practical deployment, quantum-inspired algorithms executing on classical hardware have emerged as a promising approach for solving computationally intractable problems in large-scale data analytics. This paper presents a comprehensive framework for applying quantum-inspired tensor network algorithms to complex data problems including high-dimensional clustering, feature selection, and recommendation system matrix factorization. We introduce the Quantum-Inspired Algorithm Library (QIAL), a scalable implementation that seamlessly integrates with Apache Spark and other big data frameworks. Through extensive experimentation on datasets ranging from 1 million to$\mathbf{1 0 0}$million records, we demonstrate that our approach achieves 2.6x speedup compared to classical algorithms while maintaining superior accuracy (average improvement of 2.1% across five benchmark datasets) and reduced memory footprint (up to$\mathbf{5 2 \%}$reduction). Our tensor network-based clustering algorithm shows particular promise for NP-hard combinatorial optimization problems that are currently intractable for conventional big data systems. The proposed framework opens new avenues for practical quantum-inspired computing in enterprise-scale data analytics applications.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Jan 5, 2026•0 citations

Parametrized Complexity of Quantum Inspired Algorithms

Ebrahim Ardeshir-Larijani

Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms such as quantum optimization and machine learning. Regardless of which hardware platform these novel algorithms operate on, whether it is adiabatic or gate based, from theoretical point of view, they are performing drastically better than their classical counterparts. Two promising areas of quantum algorithms quantum machine learning and quantum optimization. These are based on performing matrix operations using quantum states and operation, in order to speed up data analysis where quantum computing can efficiently work with high dimensional vectors. Motivated by that, quantum inspired algorithms (e.g. for recommendation systems and principal component analysis) are developed to cope with high dimensionality using probabilistic techniques that are inspire from quantum computing. In this paper we review recent progress in the area of quantum inspired algorithms for low rank matrix approximation. We further explore the possibility of using parametrized complexity for such algorithms to refine practical complexity analysis. Finally, we conjecture that quantum inspired algorithms that use low rank approximation and also sample and query technique for input representations are Fixed Parameter Tractable (FPT).

arXiv:2112.11686•Dec 22, 2021•0 citations

Quantum Nearest Neighbor Collaborative Filtering Algorithm for Recommendation System

Jiaye Li, Jinjing Shi, Jian Zhang +4 more

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.

ACM Transactions on Knowledge Discovery from Data•Jun 29, 2024•6 citations

Quantum-Inspired Classical Algorithms for Singular Value Transformation

Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

arXiv:1910.05699•Leibniz international proceedings in informatics•Oct 13, 2019•14 citations

Quantum-Inspired Classical Algorithm for Principal Component Regression

Daniel Chen, Yekun Xu, Betis Baheri +4 more

This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.

arXiv:2010.08626•Oct 16, 2020•3 citations
Modern recommendation systems leverage historical behavior information to generate precise recommendation results for users. However, when the data scale of users and items is large, it is difficult to generate recommendation results in time. Tang proposed a quantum-inspired recommendation algorithm, which could solve the recommendation problem in constant time complexity. However, Tang’s approach is based on a set of assumptions which rely heavily on some empirical parameters. The time complexity for calculating parameters is high. Thus, this approach cannot be directly applied in industrial applications. In this paper, we propose a method, namely, Quantum-inspired Recommendation system with threshold Proportion Interception (QRPI), which is based on the quantum-inspired recommendation system and more suitable for industrial environments. Compared with the existing widely used recommendation algorithms, we show through numerical experiments that our solution can achieve almost the same performance with better efficiency.
We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.
While full-scale quantum computers remain years away from practical deployment, quantum-inspired algorithms executing on classical hardware have emerged as a promising approach for solving computationally intractable problems in large-scale data analytics. This paper presents a comprehensive framework for applying quantum-inspired tensor network algorithms to complex data problems including high-dimensional clustering, feature selection, and recommendation system matrix factorization. We introduce the Quantum-Inspired Algorithm Library (QIAL), a scalable implementation that seamlessly integrates with Apache Spark and other big data frameworks. Through extensive experimentation on datasets ranging from 1 million to100\mathbf{1 0 0}100million records, we demonstrate that our approach achieves 2.6x speedup compared to classical algorithms while maintaining superior accuracy (average improvement of 2.1% across five benchmark datasets) and reduced memory footprint (up to52%\mathbf{5 2 \%}52%reduction). Our tensor network-based clustering algorithm shows particular promise for NP-hard combinatorial optimization problems that are currently intractable for conventional big data systems. The proposed framework opens new avenues for practical quantum-inspired computing in enterprise-scale data analytics applications.
Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms such as quantum optimization and machine learning. Regardless of which hardware platform these novel algorithms operate on, whether it is adiabatic or gate based, from theoretical point of view, they are performing drastically better than their classical counterparts. Two promising areas of quantum algorithms quantum machine learning and quantum optimization. These are based on performing matrix operations using quantum states and operation, in order to speed up data analysis where quantum computing can efficiently work with high dimensional vectors. Motivated by that, quantum inspired algorithms (e.g. for recommendation systems and principal component analysis) are developed to cope with high dimensionality using probabilistic techniques that are inspire from quantum computing. In this paper we review recent progress in the area of quantum inspired algorithms for low rank matrix approximation. We further explore the possibility of using parametrized complexity for such algorithms to refine practical complexity analysis. Finally, we conjecture that quantum inspired algorithms that use low rank approximation and also sample and query technique for input representations are Fixed Parameter Tractable (FPT).
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 l2,1−l_{2,1}-l2,1​− norm and l1−l_{1}-l1​− 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.
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.