(T) Qantamagazine has a fantastic article about the story of Erwin Tang “Major Quantum Computing Advance Made Obsolete by Teenager.”

Long story short, in her paper posted online earlier this month, 18-year-old Erwin proved that ordinary computers can deliver algorithms for recommender systems at the performance potentially comparable to those that can theoretically run on a quantum computer.

Recommender systems are a category of machine learning algorithms to provide personalized user experiences such as recommending games, books, or movies to someone, and have been popularized by the Netflix prize.

Recommender systems learn basically from a matrix of interactions between the users and the items to recommend to the users.

Different types of algorithms such as machine factorization or factorization machines re-invent that matrix to generate better features about those interactions.

Two previous researchers Iordanis Kerenidis and Anupam Prakash  proposed in 2016 a quantum algorithm for recommender systems:

“A recommendation system uses the past purchases or ratings of n products by a group of m users, in order to provide personalized recommendations to individual users. The information is modeled as an m×n preference matrix which is assumed to have a good rank-k approximation, for a small constant k. 
In this work, we present a quantum algorithm for recommendation systems that has running time O(poly(k)polylog(mn)). All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.”

Instead, Erwin proposed a quantum-inspired classical algorithm for recommendation systems that can run on none quantum computing machine:

“We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m×n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n. 
The main insight of this work is the use of simple routines to manipulate ℓ2-norm sampling distributions, which play the role of quantum superpositions in the classical setting. This correspondence indicates a potentially fruitful framework for formally comparing quantum machine learning algorithms to classical machine learning algorithms.”

What an accomplishment!

References

• Quantamagazine, “Major Quantum Computing Advance Made Obsolete by Teenager“
• Ewin Tang, “A quantum-inspired classical algorithm for recommendation systems“
• Iordanis Kerenidis, Anupam Prakash, “Quantum Recommendation Systems“
• Hacker new’s thread, “Teenager Finds Classical Alternative to Quantum Recommendation Algorithm“

Note: The picture above is Erwin.

Copyright © 2005-2018 by Serge-Paul Carrasco. All rights reserved.
Contact Us: asvinsider at gmail dot com.