How a quantum-inspired algorithm changed recommendation systems.

Recommendation systems are at the core of new digital platforms and innovative products that we encounter every day. They suggest different results or options based on data, which may encode user preferences, historical data or further information such as market profitability. Some famous examples are Netflix recommendations so that users can enjoy new blockbuster movies based on their previous choices, new products that Amazon suggests based on the consumption patterns of their customers or stocks that are profitable at a given time. Anytime you read “items you might be interested in” or “users that bought this product also enjoyed…” there may be a recommendation engine behind the scenes.

There are two major approaches to recommendation:
● Collaborative Filtering: This method makes predictions based on the user’s past
activity and similar user’s past behaviour.
● Contest-Based Filtering: This method produces recommendations based on specific
characteristics of the products.


Mathematically speaking, the collaborative filtering algorithm can be explained as a model that completes a certain matrix of small rank. Consider the following example of four users and four products:

USER 1USER 2USER 3USER 4
PRODUCT 151
PRODUCT 213
PRODUCT 353
PRODUCT 424

We would like to predict the rating that users would give those products that they have not rated yet. In order to do this, we will find similar users and infer this information from their rating. The similarity between users can be measured taking into account the common items and ratings.


This problem has been commonly believed to be computationally hard. There was a result by Kerenidis and Prakash (https://arxiv.org/abs/1603.08675, 2016) which claimed to solve this problem using a quantum algorithm in polylog(m,n) time. This was a lower bound for any classical algorithm known to that date (linear in m and n), and a strong candidate between quantum algorithms in the field of quantum machine learning.


In 2018 Ewin Tang, proposed a quantum-inspired algorithm (https://arxiv.org/abs/1807.04271) which was the classical version of the Kerenidis and
Prakash quantum algorithm. The computational cost of this classical algorithm is O(poly(k) polylog(m, n)) time, which is a clear improvement over previous algorithms. This classical recommendation system results in exponentially faster recommendations compared to previous classical algorithms.


Ewin’s quantum-inspired algorithm solves a generalized problem of the recommendation problem that we introduced previously and was inspired by the Kerenidis and Prakash quantum algorithm. It can be stated as follows: given m users and n products, partial information about product ratings and preferences, and assuming that the preference matrix is low-rank, obtain a sample of products that a given user may select.

This algorithm shows that the knowledge and intuition gained from quantum algorithms can yield quantum-inspired algorithms to solve relevant problems in classical computers now. Recommendation systems are one the areas improved by quantum-inspired algorithms, but we expect many others and further problems that can be solved more efficiently using them.