It’s not every day that an 18-year-old college student catches the eye of the computing world, but when Ewin Tang took aim at recommendation algorithms similar to those commonly used by the likes of Amazon and Netflix, the University of Texas at Austin mathematics and computer science undergraduate blew up an established belief: that classical computers cannot perform these types of calculations at the speed of quantum computers.
In a July 2018 paper, which Tang wrote for a senior honors thesis under the supervision of computer science professor Scott Aaronson, a leading researcher in quantum computing algorithms, she discovered an algorithm that showed classical computers can indeed tackle predictive recommendations at a speed previously thought possible only with quantum computers. “I actually set out to demonstrate that quantum machine learning algorithms are faster,” she explains. “But, along the way, I realized this was not the case.”
Figure. Ewin Tang set out to show that quantum machine learning algorithms are faster than classical algorithms, “but … I realized this was not the case.”
The ripples of Tang’s research have reached far and wide. Not surprisingly, the press fawned over her discovery, in some cases implying that it had made quantum computing advances obsolete. Mathematicians and computer scientists in the machine learning field took notice, too. Some acknowledged that Tang found a blind spot in previous research—an algorithm that had somehow escaped the top minds in the field. Her discovery has forced computer scientists to rethink basic assumptions about quantum machine learning, at a time when quantum computing is advancing rapidly.
Make no mistake, Tang’s research is remarkable, and it will have a significant impact on both classical and quantum machine learning. “What Ewin’s paper demonstrates is that the properties exploited by the quantum algorithm can also be used by a classical algorithm,” explains James R. Lee, a professor of computer science at the University of Washington and Tang’s Ph.D. advisor. “Ultimately, this offers a new framework for designing conventional algorithms on classical computers.”
A New Formula
The algorithm in question is one that computer scientists Iordanis Kerenidis and Anupam Prakash introduced in 2016. Their quantum computing algorithm solved theoretical recommendation problems exponentially faster than any previously known classical algorithm. It achieved a speed increase by eliminating the need to access all components in a decision-based matrix; instead, the algorithm accesses only those components most relevant for a specific person. In the case of a movie recommendation, for example, this might mean a proclivity toward French films, or a desire to watch action films or romantic comedies.
At the time, “The algorithm delivered an exponential improvement compared to the best-known classical algorithms,” says Kerenidis, a senior researcher in the Algorithms and Complexity Group at Université Paris Diderot. Essentially, the pair demonstrated that a quantum computer could process recommendation challenges exponentially faster than any known algorithm, though it didn’t eliminate the possibility of an equally fast classical algorithm. When, in 2017, Tang selected the topic for a senior honors thesis in a class Aronson taught about quantum information, she simply hoped to confirm such an outcome. “We thought that the analysis would back the validity of existing research,” she says.
A famous example of this approach is Simon’s Problem, which was created by computer scientist David Simon in 1994. It demonstrated, at least on a theoretical level, that this computational problem can be solved with exponentially fewer queries on a quantum computer. It served as the foundation for Shor’s Factoring Algorithm, which appeared shortly thereafter and remains a highly significant contribution to quantum theory. Peter Shor delivered further evidence that Simon’s concept was correct by developing a quantum algorithm for integer factorization. The algorithm finds the prime factors of an integer N in time polynomial in the number of digits of N.
Kerenidis and Prakash’s quantum computing algorithm solved theoretical recommendation problems faster than any previously known classical algorithm.
Yet as Tang studied the algorithm further, things began to get a lot more interesting. For months, she worked to rule out the possibility that a classical algorithm could address the Kerendis-Prakash problem. Aaronson refers to this as phase 1. “At the time, nothing about that failure seemed odd or anomalous to us: most likely, we thought, there was indeed no classical algorithm, but ruling it out was just a very hard problem,” he says. “At some point, though, Ewin had the key insight about why an efficient classical algorithm should exist after all and set out to develop it.” Aaronson refers to this stage as phase 2.
All along, the algorithm Kerenidis and Prakash had discovered and the validity of their calculations were never in doubt. What eventually became apparent was that there was more to the story. “It appeared that there was something other people had missed,” she states.
During the early stages of the project, Aaronson worked with Tang to further explore the mathematical underpinnings—despite the fact that he was on sabbatical during most of this period. During the latter stages, Tang worked almost entirely on her own. Finally, “We went over it and over the research because we wanted to be absolutely sure that it was sound before it was published,” Aaronson explains.
Soon after graduating, Aaronson arranged for Tang to appear at a quantum computing workshop at the Simons Institute for the Theory of Computing, part of the University of California, Berkeley (UC Berkeley). In attendance were a number of luminaries from the quantum machine learning field, including Ronald de Wolf from the University of Amsterdam, Mario Szegedy from Rutgers University, and Iordanis Kerenidis who, with Prakash, a graduate student at UC Berkeley, had written the original quantum machine learning recommendations paper.
At the symposium, the luminaries watched and listened closely for about four hours, spread across two days. They asked questions and probed, but none of them could find anything wrong with Tang’s research and calculations. Aaronson encouraged Tang to publish the paper, A Quantum-inspired Classical Algorithm for Recommendation Systems. It appeared in July 2018 at the Electronic Colloquium on Computational Complexity (ECCC) and it was later accepted to the ACM Symposium on Theory of Computing (STOC 2019). Says Kerenidis, “It is an impressive piece of theoretical work. It is very interesting to see that a quantum algorithm can inspire new classical algorithms.”
Finding the Proof
Tang’s research focused on a specific piece of the machine learning puzzle. Recommendation systems suggest products or choices based on data about user preferences. The algorithm typically revolves around a model that is based on a specific task: completing an m x n matrix of small rank k. However, Tang presented a classical algorithm that produces a recommendation in O(poly(k) polylog(m, n)) time. This represents “an exponential improvement on previous algorithms that run in time linear in m and n,” she noted in the paper.
In plain terms, Tang achieved a speedup in classical computing using the same general approach Kerenidis and Prakash tapped. She directed the algorithm to narrow the matrix and focus only on the most important criteria to generate a useful recommendation.
The belief that quantum computing produces exponential improvements over classical computing algorithms for recommendation systems had been shattered. “The best we can hope for is a polynomial improvement, but in practice this can still be of great value,” Kerenidis explains. Lee says that it’s important to view the findings in context, and not allow the short-term ramifications to distort the long-term uses and benefits of quantum machine learning. “There are two important components to the research,” he says. “First, it’s an exciting direction in algorithms research because it offers a new approach to the design of classical algorithms. Second, it’s an important step in mapping out the types of problems where we could expect quantum computers to be exponentially more efficient than classical computers.”
In fact, the recommendation problem is only a tiny sliver of the quantum computing universe. Says Bob Sutor, vice president for IBM Q Strategy and Ecosystem at IBM Research (which unveiled the first commercially available quantum computer in January 2019): “While it might be fun to set up some sort of competition between classical and quantum algorithm creators, the truth is that they work with and inspire each other… there is a real separation in some cases between classical and quantum.”
By the Numbers
Beyond the obvious appeal of an 18-year-old deflating the quantum machine learning balloon lies a basic fact. “It would be very shortsighted to view this research as any sort of setback for quantum computing,” Lee points out. “This is essentially how scientific research works and, over the long run, this research helps us better understand how and where to use classical computing methods and quantum computing methods. This doesn’t fundamentally change the viability of quantum computing. It hasn’t made the field any less promising.”
Aaronson concurs. “Ewin’s break-through rules out the hope of an exponential quantum speedup for certain types of machine learning problems. But there are many other applications of quantum computers that are not affected by it—including breaking cryptographic codes, getting modest speedups for optimization problems, and probably most important of all, simulating quantum physics and chemistry themselves.”
Amid all the claims and counter-claims, it is important to keep a few things in mind. There is strong evidence that quantum computing can significantly accelerate certain computations, but there is no definitive proof of such. The only known provable separation theorem between quantum and classical is sqrt(n) vs. n. Proofs of stronger separation between classical and quantum are relative to an oracle.
There is also a long way to go before quantum computing becomes a reality. The IBM Q has only 20 qubits, meaning that at this point, it is more of a demonstration machine than a viable quantum computing device. Finally, whether quantum or classical computing devices are used, machine learning requires very large input sets.
Tang is taking things in stride. She is now pursuing her doctorate in theoretical computer science from the University of Washington, where she continues to explore quantum and classical algorithms. She has since collaborated on a second academic paper focusing on classical sub-linear-time algorithms that are designed to solve low-rank linear systems of equations. And she finds comments from a handful of detractors, upset that she chose to focus on a problem that helps companies make money, “amusing.”
Concludes Tang, “At this point, it’s not clear whether a broader group of quantum algorithms or techniques can be dequantized and applied to make classical algorithms faster.”
Further Reading
Tang, E.
A Quantum-inspired Classical Algorithm for Recommendation Systems, Electronic Colloquium on Computational Complexity (ECCC), July 2018. https://arxiv.org/abs/1807.04271
Kerenidis, I., and Prakash, A.
Quantum Recommendation Systems, September 2016. https://arxiv.org/abs/1603.08675
Aaronson, S.
Quantum Computing Since Democritus, Cambridge University Press. 2013. https://www.scottaaronson.com/democritus/
Ciliberto, C., Herbster, M., Ialongo, A.D., Pontil, M., Rocchetto, A., Severini, S., and Wossnig, L.
Quantum Machine Learning: a Classical Perspective, Quantum Physics, Volume 474, Issue 2209, page 20170551. January 1, 2018. https://royalsocietypublishing.org/doi/full/10.1098/rspa.2017.0551
Join the Discussion (0)
Become a Member or Sign In to Post a Comment