A very recent discovery in the area of quantum computing surprised me (and the community) a lot.

Ewin Tang, a 18 years-old female student at Texas University, recently proved that classical computers can solve the “recommendation problem” (an NP- hard problem with practical appeal, used e.g. In Netflix systems, and others) as fast as quantum computers. This is a very significant result, because the “recommendation problem” was taken to be the best example of quantum speedup, that is, of an algorithm that quantum computers could solve in much less tine than standard algorithms. Her proof reverts the expectation about the absolute usefulness of quantum computers.

As Scott Aaronson, her advisor for graduate degree explains, given a matrix with m users and n products representing incomplete data about users opinions (one to five stars) about movies or products, organized into a convenient binary tree data structure, the problem is to sample some movies or products that a given user is likely to want to buy or to see. This is (in abstract form) the problem that Amazon and Netflix need to solve every time they tell you which books or movies you “might enjoy.”

Here is a link for Tang’s paper at ECCC – TR18-128; she was able to show that “recommendation problem” can be solved exponentially faster than anything known before. What is stunning is that she solved this problem by modifying a quantum algorithm, developed for a quantum computer, and made it run on a classical computer. Of course, it is important to know whether. other quantum algorithms could be modified in analogous way. May be quantum computers are not so revolutionary as we have been thinking up to now…