Allen School Ph.D. student Ewin Tang has landed a spot on Forbes’ 2019 list of “30 Under 30” in science for developing a method that enables a classical computer to solve the “recommendation problem” in roughly the same time that a quantum computer could — upending one of the most prominent examples of quantum speedup in the process. Her algorithm offers an efficient solution to a core machine learning problem which models the task of predicting user preferences from incomplete data based on people’s interactions with sites such as Amazon and Netflix.
Tang, who arrived at the University of Washington this past fall to work with professor James R. Lee in the Theory of Computation group, tackled the recommendation problem as an undergraduate research project while at the University of Texas at Austin. The project was an outgrowth of a quantum information course she took with UT Austin professor Scott Aaronson, who challenged her to prove that no fast classical algorithm exists for solving the problem. He was inspired to set this particular challenge after Iordanis Kerenidis and Anupam Prakash — researchers at Université Paris Diderot and University of California, Berkeley, respectively — published a quantum recommendation algorithm that could solve the problem exponentially faster than a classical computer could, in part by relying on a randomized sample of user preferences rather than attempting to reconstruct a full list, in fall 2016. But they did not prove definitively that no such classical algorithm existed.
Enter Tang and Aaronson. According to an article about Tang’s discovery that appeared last summer in Quanta Magazine, Aaronson believed that a comparable algorithm didn’t exist, and that his student would confirm Kerenidis’ and Prakash’s discovery. But as Tang worked through the problem during her senior year, she started to believe that, actually, it did exist. After Tang presented her results at a workshop at UC Berkeley that June, other members of the quantum computing community agreed — confirming it as the fastest-known classical algorithm and turning a two-year-old discovery on its head.
Or, as Tang recently explained to GeekWire, “We ended up getting this result in quantum machine learning, and as a nice side effect a classical algorithm popped out.”
The quantum algorithm relies on sampling to make the process of computing high-quality recommendations more efficient, built on the assumption that most users and their preferences can be approximated by their alignment with a small number of stereotypical user preferences. This approach enables the system to bypass reconstruction of the complete preference matrix, in which many millions of users and elements may be represented, in favor of honing in on the highest-value elements that matter most when giving recommendations. Tang employs a similar strategy to achieve similar results — proving that a classical algorithm can produce recommendations just as well – and nearly as fast – as the quantum algorithm can, without the aid of quantum computers.
According to Tang’s Ph.D. advisor, Lee, her achievement extends far beyond the original question she set out to answer.
“Ewin’s work provides more than just a (much) faster algorithm for recommendation systems — it gives a new framework for the design of algorithms in machine learning,” Lee said. “She and her collaborators are pursuing applications in clustering, regression, and principal component analysis, which are some of the most fundamental problems in the area. Her work is also a step toward clarifying the type of structure quantum algorithms must exploit in order to achieve an exponential speedup.”
Check out Tang’s Forbes profile here and a related GeekWire article here. Read the original story of her discovery in Quanta Magazine here.
Way to go, Ewin!