  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 \times 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(\text{poly}(k)\text{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.
