A serious success in quantum computing prevented teen

18-year-old Yuvin Tan proved that classic computers can solve the “task of recommendations” almost as quickly as quantum computers. This result cancels one of the best examples of quantum acceleration of calculations.

A teenager from Texas laid siege to the development of quantum computing. In a paper published this month on the Internet , 18-year-old Yuvin Tan proved that ordinary computers can solve an important computational problem at a speed potentially comparable to quantum computers.

In the most practical way, the problem of recommendations is related to how services like Amazon and Netflix determine which products you might like. Computer scientists considered it one of the best examples of problems which can be solved on quantum computers exponentially faster - that emphasizes the potential opportunities of these futuristic machines. And now Tan refuted this opinion.

“It was one of the defining examples of quantum acceleration — and now it has disappeared,” says Tan, who graduated from the University of Texas at Austin in the spring, and who begins his preparation for a doctoral degree at the University of Washington this fall.

In 2014, at the age of 14, Tang jumped over through 4, 5, and 6 grades, and entered the University of Texas, where he graduated from mathematics and computer science. In the spring of 2017, Tan passed a quantum information course where Scott Aaronson , a renowned researcher in the field of quantum computing , taught . Aaronson recognized an unusually talented student in Tanya and invited him to become his adviser in an independent research project. Aaronson gave Tanu several tasks to choose from, including the problem of recommendations. Tang chose her somewhat reluctantly.

“I hesitated because it seemed rather difficult, but it was the simplest of all the tasks that he offered me,” said Tan.

The task of the recommendations is to issue recommendations on products that the user might like. Consider Netflix. He knows which films you watched. He knows that millions of his users have watched. With such information, can you find out what you want to look next?

This data can be represented in the form of a huge grid, or a matrix, on top of which all films are listed, on the side - all users, and inside there are values ​​that estimate how much each user likes each film. A good algorithm will produce a list of recommendations, quickly and accurately finding similarities between films and users, and filling in the empty cells of the matrix.

In 2016, computer scientists Iordanis Kerenidis and Anupam Prakash published a quantum algorithm that solved the problem of recommendations exponentially faster than any of the known classical algorithms. They received such a quantum acceleration, in particular, by simplifying the problem. Instead of filling out the entire matrix, and identifying the single best product for a recommendation, they came up with a way to divide users into a small number of categories - do they like blockbusters or independent movies? - and to process the existing data so as to issue a recommendation, which would simply be quite good.

By the time the work of Kerenides and Prakash appeared, there were very few examples of tasks that quantum computers had to solve exponentially faster than classical ones. For the most part, these tasks were specialized — narrow problems specifically designed to take advantage of the strengths of quantum computers (including the " fortification " problem , which we have already mentioned ). The work of Kerenides and Prakash turned out to be interesting because it covered a real problem, important for people, in which quantum computers overtook classical ones.

“From my point of view, it was one of the first examples of machine learning and big data processing, in which we showed that quantum computers can do something that we don’t yet know how to make using classical methods,” said Kerenides, an expert on informatics from the Research Institute of the Basics of Informatics of Paris.

Kerenides and Prakash proved that a quantum computer can solve the problem of recommendations exponentially faster than any of the known algorithms, but they did not prove that there is no fast classical algorithm. Therefore, when Aaronson began working with Tan in 2017, he set such a task - to prove the absence of a fast classical algorithm, confirming the quantum acceleration of Kerenides and Prakash.

“It seemed to me that this would be an important point that we will put in order to complete this story,” said Aaronson, who at that time believed that there is no fast classical algorithm.

Tan began working on this in the fall of 2017, hoping that the task of the recommendations would be the subject of his dissertation. For several months, Tan tried to prove the impossibility of the existence of a classical algorithm. Time passed, and Tan began to think that perhaps such an algorithm did exist.

“I started to believe in the existence of the classical algorithm, but I couldn’t convince myself of this, because Scott thought it didn’t exist, and he was an authority for me,” said Tan.

Finally, when the dissertation deadline was already pressing, Tan wrote a letter to Aaronson, where he confessed his growing suspicions. “Tan wrote to me, essentially, the following: I think that a fast classical algorithm exists,” said Aaronson.

Throughout the spring, Tan wrote down the results and worked with Aaronson to clarify some steps of the proof. The fast classical algorithm discovered by Tan was inspired by the fast quantum algorithm found by Kerenides and Prakash two years before. Tan demonstrated that the quantum sample used in their algorithm can be reproduced under classical conditions. The Tana algorithm, like the Kerenidis and Prakash algorithm, was executed in polylogarithmic time — that is, the computation time was estimated by the logarithm of parameters such as the number of users and products — and was exponentially faster than any other previously known classical algorithm.

After Tan’s completion of the algorithm, Aaronson wanted to verify its correctness before publishing. “I was still nervous about the fact that if, after Tan’s publication, she’s wrong, the first big job in Tan’s career would be zilch,” said Aaronson.

Aaronson planned to attend a meeting on quantum computing at the University of California at Berkeley in June. The luminaries of this region were to meet there, including Kerenides and Prakash. Aaronson invited Tan to Berkeley with him in order to informally present his algorithm after the official part of the conference.

On the morning of June 18 and June 19, Tang read two lectures, answering questions from the audience. After four hours, a consensus was developed: Tahn’s classical algorithm resembles the correct one. What many present didn’t understand was how much Tang was young. “I didn’t know that Yuvin was 18 years old, and I certainly didn’t think so by the results of the conversations. It seemed to me that Yuvin was leading the conversation as a fully grown man, ”said Kerenides. Now the algorithm will have a formal expert assessment before it is published.

For quantum computation, the result of Tan is a step backwards. Or not. Tang eliminated one of the clearest and best examples of quantum advantage. At the same time, Tana’s work is further evidence of the fruitful interactionresearch of classical and quantum algorithms.

“Tang eliminates the quantum acceleration of Kerenides and Prakash, but in another sense, Tang contributes to great improvement and is based on their work. Tang would never have invented his classical algorithm if they had not published their quantum algorithm, ”said Aaronson.