A teenager from Texas has taken quantum computing down a 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 potentially comparable to that of a quantum computer.
In its most practical form, the “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.
All episodes Your browser does not support the audio element. / APPLE SPOTIFY
“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.
“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. A good algorithm would generate recommendations by quickly and accurately recognizing similarities between movies and users and filling in the blanks in the matrix.
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 (these include the “forrelation” problem Quanta covered earlier this year). Kerenidis and Prakash’s result was exciting because it provided a real-world problem people cared about where quantum computers outperformed classical ones.
... continue reading