  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.
