Ewin Tang, an 18-year-old, has now successfully proven that quantum computers are not faster than classical computers when it comes to solving the recommendation problem.
The teenager’s result is important because it effectively gets rid of one the best quantum speedup examples.
Ewin Tang, just a teenager living in Texas, took the opportunity to study the field of quantum computing and take it down a notch.
The 18-year-old posted a paper online about a month ago and managed to prove that there was nothing stopping ordinary computers from competing with quantum computers when it came to solving important computer problems.
She argued that classical computers could match the performance potential of quantum computers.
One of the problems that Ewin Tang tackled was the recommendation problem.
The recommendation problem is perhaps one of the most practical forms of computing problems.
This problem is related to online services (such as Netflix and Amazon) and how they go about determining the kind of content and products that the user may want to try out and use.
Before Ewin Tang’s proof, the majority of the computer scientists considered the recommendation problem as a representative problem that showed how quantum computers could solve some computing problems exponentially faster than classical computers.
With Ewin Tang’s proof, she has managed to strip away that validation.
Tang managed to graduate from the prestigious University of Texas, Austin last spring.
She is also expected to begin his Ph.D program this fall at the University of Washington.
Tang mentioned that previous work in the field represented the most definitive example of quantum speedup and because of his work, it was no longer valid.
About four years ago when Tang was just 14, she skipped some grades (fourth, fifth and sixth to be more precise) and enrolled at UT Austin.
There she majored in computer science and mathematics.
Then, in the spring of last year (that is, 2017) Tang decided to take a class on quantum information.
A prominent researcher in the field of quantum computing, Scott Aaronson, taught that class.
As expected, Scott Aaronson quickly recognized Erwin Tang as a smart and unusually talented science student.
Seeing his potential, Scott also offered his services as an adviser to Tang to work on an independent research-based project.
Tang received a handful of problems from Aaronson to try and solve.
The problem set included the previously-mentioned recommendation problem.
Tang did choose the recommendation problem but she did so rather reluctantly.
Recently Erwin Tang mentioned that she did have some hesitancy because the recommendation problem really looked like a hard problem from his perspective.
However, the same problem represented the easiest of all the problems that Scott Aaronson gave Tang to solve.
As mentioned at the top as well, the recommendation problem, in its design, is simple enough.
It is meant to provide recommendation for products and services/content that online consumers would like.
The case of Netflix perfectly fits this problem.
Netflix, by default, knows what kind of films the user has watched.
The service also has significant information on what millions of other users on the network have watched as well.
Using all this information, the algorithms working behind Netflix try to figure out what the user is likely to watch next.
It tries to guess the user’s desires and wants.
For simplicity, readers should think of all this data having a particular arrangement.
That arrangement is that of a giant grid.
Some like to refer to it as a matrix.
The matrix lists users down one side and lists movies all across the top.
This same matrix also has points with values on the grid.
What do these values represent?
These values try to quantify whether or not (and to what extent precisely) a given user would like a given film.
Any complex algorithm would hardly find it difficult to recommend movies and TV shows rather quickly and most of the time, accurately by recognizing similarities between users and movies.
Then the algorithm would fill in all the required blanks in the given matrix.
That quantum algorithm beat any and all known classical algorithms at solving the above-mentioned recommendation problem.
In other words, the quantum algorithm did so exponentially faster than the slow classical algorithms.
How did the researchers achieve this?
Well, there were many factors at play.
But in order to achieve the quantum speedup that these researchers wanted to achieve, they first simplified the given problem.
So instead of going the route where the algorithm had to fill out the whole of the matrix and then being to identify the single and unique best content/product to recommend, the two computer scientists mentioned above developed a novel way of successfully sorting viewers/users into a slightly small number of movies/content categories.
In even simpler terms, the algorithm looked at whether or not the user in question liked to watch indie films or blockbusters.
After that, the algorithm sampled the already existing user data in order to quickly generate a good enough recommendation.
Now, at the time when Prakash and Kerenidis came out with their research paper, computer scientists only new a few number of examples that represented problem which quantum computers seemed to have the ability to solve much more quickly (in fact, exponentially faster) than normal/classical computer machines.
Readers should also understand that most of such problems were highly specialized.
In other words, computer scientists had narrowed down problems that they had designed in order to play to the exact strengths of the new machines that we call quantum computers.
The set of new problems also included the Forrelation problem.
Click here to read more about that.
The reason why Prakash and Kerenidis received so much attention from the community was that they showed how quantum computers could outperform classical computers at a real-world problem and a problem that people really cared about.
That is what made the results that Kerenidis and Prakash achieved so exciting.
Kerenidis who works in Paris at the Research Institute of the Foundations of Computer Science as a computer scientist recently said that to his senses the recommendation problem represented one of the first examples in big data and machine learning where researchers managed to show that quantum computer really could do something that researchers did not know how to do on classical machines.
Prakash and Kerenidis had earlier proved that no known classical algorithm could match a quantum computer machine in solving the recommendation problem.
As mentioned before, a quantum machine could solve the recommendation problem exponentially faster than these classical machines.
However, these two computer scientists didn’t really prove that a faster classical algorithm could never exist.
That leads to the year 2017 when Tang started to work with Aaronson.
Aaronson posed this question and wanted Tang to solve this.
He posed the question to prove that there really was no faster classical recommendation algorithm.
In the process of doing so, he would also confirm that Prakash and Kerenidis’ quantum speedup was indeed real.
Aaronson told the media, to him, the problem seemed like an important “t” to simply cross and then complete the related story.
At the time Aaronson held this belief that no faster classical algorithm existed anywhere which could match the performance potential of a quantum algorithm.
Tang started to work on the recommendation problem in the fall of the year 2017.
He intended to use the recommendation problem as his senior thesis.
Tang worked on the recommendation problem for several months and struggled in order t prove that there was no possibility of a faster classical algorithm.
As more and more time went by, Ewin Tang started to have an idea on how there could be a classical algorithm that could perform as fast as a quantum algorithm.
Tang recently said that she started to believe that there was a faster classical algorithm.
However, according to Tang, she could not develop the problem enough to prove it to himself.
She couldn’t do so because Scott (her adviser) seemed to have this idea that there really wasn’t one and Tang considered Scott to be the authority.
With Tang’s senior thesis deadline approaching fast, she finally decided to write to Scott Aaronson.
Tang admitted his growing admission.
Aaronson mentioned that Tang wrote to him and told him that she thought there existed a fast classical algorithm.
After that, Tan spent the entire supper in writing up results and working with Scott Aaronson in order to clarify a few of the steps involved in the proof.
The fast quantum algorithm that Prakash and Kerenidis had managed to find just two years earlier served as a direct inspiration for Tan to develop his own fast classical algorithm.
In his proof, Tang successfully showed that she could replicate the type of techniques related to quantum sampling that Prakash and Kerenidis used in their quantum algorithm in a classical setting as well.
Similar to Prakash and Kerenidis’ algorithm, the classical algorithm from Tang also ran in polylogarithmic time.
What does that mean?
That means the total computation time directly scaled with the logarithm of all related characteristics such as the total number of products and users in the given data set.
This is how the algorithm from Tan came to be exponentially faster and more efficient than any classical algorithm known previously.
Now, even after having written the algorithm, Tang and Aaronson weren’t quite ready to move ahead.
After seeing Tang completing the algorithm, Scott Aaronson wanted to make sure that the algorithm indeed returned the correct results.
Aaronson only wanted to release the algorithm to the public after ensuring that fact.
He told reporters that he went through a period of nervousness once he came to the realization that once Tang had uploaded the paper online and it turned out to give the wrong result, the first important paper of Erwin Tang’s career would go completely splat.
Before the paper came out Scott Aaronson had actually planned to attend the University of California, Berkeley for a quantum computing workshop in June.
Reports say that a lot of the big names in the quantum computing field had had also made plans to attend the workshop including the two computer scientists mentioned above (Prakash and Kerenidis).
This is when Aaronson made the decision to invite Erwin Tang to Berkeley and present his classical algorithm to the people there a few days after the quantum computing conference had ended.
Tang came and gave two lectures on the mornings of June 19 and June 18.
She also fielded some questions from the present audience.
And after around four hours of that and more, the audience seemed to have come to a consensus:
The classical algorithm that Tang had presented them seemed pretty correct.
However, a lot of people present in the room failed to realize one important aspect of the whole situation:
The speaker was incredibly young.
Kerenidis recently told reporters that he did not have any idea that Ewin Tang was just 18.
He also said he certainly did not realize that from the talk that Tang gave.
Furthermore, Kerenidis said, to him, Ewin Tang looked like someone who had enough understanding of the subject to give a very mature lecture.
Tang can’t publish his research paper just yet.
First, the algorithm will have to face a formal peer review.
Only after that can it go to the publication stage.
As far as quantum computing is concerned, the result that Tang has managed to develop is a major setback.
Or perhaps it is not.
But the fact is, Tang (despite her age) has managed to eliminate one of the most important and clearest examples of where quantum computers seemed to have a great advantage over classical computers.
With that said, it is also true that Erwin Tang’s research paper is just one of the many papers that provide further evidence that there is a pretty fruitful interplay between classical algorithms and the study of quantum computing.
According to Aaronson, Tan’s research paper has killed Prakash and Kerenidis’ quantum speedup research.
However, he said, in another sense, Erwin Tang has managed to give them a big improvement and an opportunity to build upon what they have done before.
Aaronson also believes that Tang would never have gotten the opportunity to come up with his own classical algorithm had Prakash and Kerenidis not presented their own quantum algorithm.
There Aren’t Enough Geniuses
Another genius is Constantinos Daskalakis.
He is also a theoretical computer scientist.
Daskalakis is different from Tang in the sense that he has already managed to win Rolf Nevanlinna Prize.
Why did he win it?
He won it for analyzing and developing core questions in the field of machine learning and game theory.
All that one has to do in order to look at the achievements of Daskalakis is to go to his official web page here.
And then scroll down till one reaches the bottom of the page.
What’s at the bottom of the page?
The bottom of the page has links to Daskalakis past research papers in the field of theoretical computer science.
Additionally, the page also shows the name of his doctoral students at the university he now teaches at:
Massachusetts Institute of Technology.
Even below that, one can easily find a poem.
A poem that was written by Constantine Cavafy called The Satrapy.
Daskalakis has a very specific purpose for the poem.
It serves the role of a talisman for him.
Daskalakis seems to think that the poem guards him against all types of base motives.
He recently told a reporter that he uses the poem as a moral compass if one could call it that.
Daskalakis also said that he wanted to have such kind of a constant reminder that there were some really noble ideas that the was serving.
The poem, according to Daskalakis, also enables him to not forget why he made some decisions.
One may ask, what kind of decisions is Daskalakis talking about?
Well (of course?), the 37-year-old is talking about the decisions that he has managed to make over the course of his entire career.
We’re talking about decisions such as managing to forge a pretty lucrative job straight out of university and also trying to successfully pursue the hardest given problems in the field that he has chosen to spend his time in.
All of these decisions have helped Daskalakis to uncover some really distant truths.
He recently said that it all originated from an extremely deep need to make sense of something.
Furthermore, he said, when one has a mindset like his, one simply doesn’t stop unless and until one understands something and one’s brain simply cannot remain still unless and until one understands.
As mentioned before as well, this is the kind of mindset that has enabled Daskalakis (through his contributions to the field) to get widespread recognition with awards such as the Rolf Nevanlinna Prize.
This award is only given every four years.
People in the community consider it to be amongst the highest of honors that one can receive in the field of theoretical computer science.
In fact, the award itself takes the burden of citing Daskalakis’ powerful body of results.
As alluded to before, his results explicate some of the very core questions that are present in economics about how various given rational players like to behave in markets and games.
More recently though, his work has been in the field of machine learning.
To read more about this particular story, click here.