Scroll Top

A teenagers revolutionary algorithm busted quantum computings greatest promise

futurist_algorithms

WHY THIS MATTERS IN BRIEF

Quantum computers promise amazing performance gains over classical computers, but a new algorithm just put the ball back in the classical computer’s court.

 

A teenager from Texas has single handedly taken one of the biggest advances promised by the first generation of quantum computers down a notch, a big notch. In a paper posted online earlier this month, 18 year old Ewin Tang proved that ordinary computers can solve an important computing problem with performance that rivals that promised by quantum computers.

 

RELATED
Chinese researchers show off transistor gates that are just one carbon atom wide

 

In its most practical form, the so called “recommendation problem” relates to how services like Amazon and Netflix determine which products you might like to try. Computer scientists had considered it to be one of the best examples of a problem that’s exponentially faster to solve on quantum computers — making it an important validation of the power of these futuristic machines. Now Tang has stripped that validation away.

“This was one of the most definitive examples of a quantum speedup, and it’s no longer there,” said Tang, who graduated from the University of Texas, Austin, in spring and will begin a Ph.D. at the University of Washington in the fall.

In 2014, at age 14 and after skipping the fourth through sixth grades, Tang enrolled at UT Austin and majored in mathematics and computer science. In the spring of 2017 Tang took a class on quantum information taught by Scott Aaronson, a prominent researcher in quantum computing. Aaronson recognized Tang as an unusually talented student and offered himself as adviser on an independent research project. Aaronson gave Tang a handful of problems to choose from, including the recommendation problem. Tang chose it somewhat reluctantly.

 

RELATED
FDA approves first spray on skin treatment for burns

 

“I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me,” Tang said.

The recommendation problem is designed to give a recommendation for products that users will like. Consider the case of Netflix. It knows what films you’ve watched. It knows what all of its other millions of users have watched. Given this information, what are you likely to want to watch next?

You can think of this data as being arranged in a giant grid, or matrix, with movies listed across the top, users listed down the side, and values at points in the grid quantifying whether, or to what extent, each user likes each film – the same type of matrix analysis that researchers elsewhere created a new “revolutionary” quantum machine learning algorithm for a few months ago that was the focus of another of my articles. A good algorithm would generate recommendations by quickly and accurately recognizing similarities between movies and users and filling in the blanks in the matrix.

 

RELATED
Someone just built an insane 80 storey tall working 8 Bit computer in Minecraft

 

In 2016 the computer scientists Iordanis Kerenidis and Anupam Prakash published a quantum algorithm that solved the recommendation problem exponentially faster than any known classical algorithm. They achieved this quantum speedup in part by simplifying the problem: Instead of filling out the entire matrix and identifying the single best product to recommend, they developed a way of sorting users into a small number of categories — do they like blockbusters or indie films? And sampling the existing data in order to generate a recommendation that was simply good enough.

At the time of Kerenidis and Prakash’s work, there were only a few examples of problems that quantum computers seemed to be able to solve exponentially faster than classical computers. Most of those examples were specialized — they were narrow problems designed to play to the strengths of quantum computers. Kerenidis and Prakash’s result was exciting because it provided a real world problem people cared about where quantum computers outperformed classical ones.

“To my sense it was one of the first examples in machine learning and big data where we showed quantum computers can do something that we still don’t know how to do classically,” said Kerenidis, a computer scientist at the Research Institute on the Foundations of Computer Science in France.

 

RELATED
Scientists turned live bacteria into the world's first biological computer

 

Kerenidis and Prakash proved that a quantum computer could solve the recommendation problem exponentially faster than any known algorithm, but they didn’t prove that a fast classical algorithm couldn’t exist. So when Aaronson began working with Tang in 2017, that was the question he posed — prove there is no fast classical recommendation algorithm, and thereby confirm Kerenidis and Prakash’s quantum speedup is real.

“That seemed to me like an important ‘t’ to cross to complete this story,” said Aaronson, who believed at the time that no fast classical algorithm existed.

Tang set to work in the fall of 2017, intending for the recommendation problem to serve as a senior thesis. For several months Tang struggled to prove that a fast classical algorithm was impossible. As time went on, Tang started to think that maybe such an algorithm was possible after all.

“I started believing there is a fast classical algorithm, but I couldn’t really prove it to myself because Scott seemed to think there wasn’t one, and he was the authority,” Tang said.

 

RELATED
Scientists accidentally 3D printed the world's first liquid magnets

 

Finally, with the senior thesis deadline bearing down, Tang wrote to Aaronson and admitted a growing suspicion: “Tang wrote to me saying, actually, ‘I think there is a fast classical algorithm,’” Aaronson said.

Throughout the spring Tang wrote up the results and worked with Aaronson to clarify some steps in the proof. The fast classical algorithm Tang found was directly inspired by the fast quantum algorithm Kerenidis and Prakash had found two years earlier. Tang showed that the kind of quantum sampling techniques they used in their algorithm could be replicated in a classical setting. Like Kerenidis and Prakash’s algorithm, Tang’s algorithm ran in polylogarithmic time — meaning the computational time scaled with the logarithm of characteristics like the number of users and products in the data set — and was exponentially faster than any previously known classical algorithm.

Once Tang had completed the algorithm, Aaronson wanted to be sure it was correct before releasing it publicly. “I was still nervous that once Tang put the paper online, if it’s wrong, the first big paper of [Tang’s] career would go splat,” Aaronson said.

 

RELATED
Soldiers digital twins let US Army 3D print replacement body parts in battle

 

Aaronson had been planning to attend a quantum computing workshop at the University of California Berkeley, in June. Many of the biggest names in the field were going to be there, including Kerenidis and Prakash. Aaronson invited Tang to come out to Berkeley to informally present his algorithm in the days after the official conference ended.

On the mornings of June 18 and 19 Tang gave two lectures while fielding questions from the audience. By the end of four hours, a consensus emerged: Tang’s classical algorithm seemed correct. What many people in the room didn’t realise, however, was just how young the speaker was.

“I did not know Ewin was 18, and I certainly did not get that from the talk. To me [Ewin] was someone who was giving a very mature talk,” Kerenidis said. The algorithm now faces a formal peer review before publication.

 

RELATED
The personal trainers in this new gym are all AI

 

For quantum computing, Tang’s result is a setback. Or not. Tang has eliminated one of the clearest, best examples of a quantum advantage. At the same time, Tang’s paper is further evidence of the fruitful interplay between the study of quantum and classical algorithms.

“Tang is killing [Kerenidis and Prakash’s] quantum speedup, but then in another sense Tang is giving a big improvement and building on what they did. Tang never would have come up with this classical algorithm but for their quantum algorithm,” Aaronson said.

Related Posts

Leave a comment

You have Successfully Subscribed!

Pin It on Pinterest

Share This