Transcription
In the summer of 2018, the Simons Institute for the Theory of Computing at the University of California, Berkeley, hosted an exclusive gathering of the most brilliant mathematical minds on the planet. They had assembled in a seminar room to hear a presentation that threatened to dismantle a massive pillar of quantum computation. Standing before this audience of elite physicists and computer scientists was Ewin Tang. She was eighteen years old. Tang had just finished her undergraduate degree at the University of Texas at Austin. She stood at the front of the room, ready to deliver two lectures spread across four hours of intense mathematical combat. Ewin Tang was challenging one of the biggest financial and scientific ideas in technology. For years, tech firms have claimed that quantum computers could perform certain real-world tasks much faster than conventional computers. At the center of this promise was a well-known quantum algorithm made for recommendation systems. This belief led to billions of dollars in venture capital funding for quantum computer development. Tang presented a classical algorithm that matched the speed of its quantum version. She showed that if both normal and quantum computers had similar ways to access data, the quantum computer’s speed advantage disappeared. Quantum advantage is the idea that quantum machines can solve some problems much faster than classical computers. Recommendation systems are important because they show a clear business use, not just a theoretical result. The experts in the room did not go easy on her because she was young. The presentation turned into four hours of tough questions. The experts examined every part of her math and every assumption about data access. Among the audience sat Iordanis Kerenidis. Two years earlier, Kerenidis and his colleague Anupam Prakash had authored the exact quantum algorithm that Tang was now taking apart. As the hours dragged on, the audience tested the boundaries of her logic, consensus emerged that Tang’s algorithm held up. Kerenidis was really impressed, saying the presentation was so polished he didn't even realize the speaker was just eighteen. By the end of day two, everyone agreed: the math checked out, and her classic algorithm worked. This proof shot Tang right up to the top tier of theoretical computer science. She landed a spot on the Forbes Thirty Under Thirty science list and later snagged the Maryam Mirzakhani New Frontiers Prize from the Breakthrough Prize organization. This is one of the most prestigious prizes for young mathematicians. The best part, she is just getting started.
To understand the magnitude of what happened in that Berkeley seminar room, we need to take a look at the fever dream that has gripped the tech sector in the late twenty tens. Billions of dollars from venture capitalists and government defense agencies were flowing into quantum computing. The central thesis driving this gold rush was the concept of quantum advantage. The theory promised that certain tasks would run dramatically faster on quantum machines. A normal computer processes information in binary bits. These bits exist as either a zero or a one. A quantum computer, on the other hand, uses qubits, which exist in a superposition of states. A common misconception is that a quantum computer works by trying all possible solutions at once. This is not how it works. A quantum computer uses the rules of quantum mechanics, such as superposition and interference, to choreograph probabilities. A well-designed algorithm makes the paths leading to incorrect answers cancel each other out while the paths leading to the correct answer amplify each other. When a scientist measures the system, the correct answer emerges. Theoretical computer scientists had already proven that quantum machines could achieve exponential speedups for a few specific mathematical puzzles. But not all of these are speed ups are useful from a commercial point of view. So quantum computing firms desperately wanted to prove that quantum computers could achieve an exponential leap in practical commercial tasks. As a result, Machine learning became the ultimate battleground. Tech giants needed better ways to process massive data arrays for prediction and optimization. In 2016, Iordanis Kerenidis and Anupam Prakash published a paper that promised this. They introduced a quantum algorithm for recommendation systems. This was a crisp and highly visible example of a quantum win on a real-world task. The algorithm claimed an exponential speedup. An exponential leap in computer science is the ultimate prize. A polynomial speedup means an algorithm scales somewhat better. An exponential speedup means a calculation that would take the lifetime of the universe on a normal computer could be completed in minutes on a quantum machine. The Kerenidis and Prakash algorithm was a theorem, but there is a huge difference between a theorem and a physical demonstration. A theorem is a mathematical proof that a machine could theoretically perform a task. A demonstration requires actual hardware. So, the Kerenidis and Prakash algorithm gave the industry a poster child. If the right hardware can be developed, then the Kerenidis and Prakash algorithm would produce exponential gains and make all the investments worth it, by solving a real-world problem.
This was the backdrop when Ewin Tang entered when she registered for a college class in the spring of 2017. The mind that would eventually humble the quantum computing experts comes from Texas. Tang was born in the year 2000. She was really smart, moving through school incredibly fast when she was young. She skipped the fourth, fifth, and sixth grades. By the time she was ten years old, she had scored an astounding 1920 on the SAT. That same year, her parents and school officials arranged for her to enroll in courses at the University of Texas at Arlington. Her parents were great at encouraging her and letting her explore freely without pushing her into a specific field. Her father Liping Tang worked as a bioengineering professor at the university and served as the chief technology officer at a biotechnology startup named Progenitec. Her mother, Wen Jing Hu, was the founder and chief executive officer of that same startup. Having an immensely bright child brings its own challenges. Her father said in an interview with the university alumni magazine that placing a ten year old in college is a gray area with no instruction manual. Nonetheless, having her parents on campus provided a built in support system. Tang went beyond taking classes. She got into actual laboratory work. Before she was old enough to apply for a driver's permit, she was working with her mother in her father's nanotechnology laboratory. They developed in vivo imaging techniques for biomedical research. They built optical probes designed to view polarized macrophages during foreign body reactions and detect real time neutrophil responses to bacterial infections. In 2014, at the age of fourteen, Tang enrolled at the University of Texas at Austin. She pursued a double major in mathematics and computer science. Ewin's young age on campus definitely got people's attention. Her classmates often noticed this small, young person up front, nailing the professor's questions every time. They'd ask how old she was and sometimes snap a picture. Tang has said that while the age difference meant she couldn't become best buddies with her older classmates, they were fully open to working together once they saw how smart she was.
To grasp what Tang actually accomplished, take a look at Netflix. The streaming giant has millions of users and thousands of movies. Each user has only watched and rated a tiny fraction of the available catalog. The service needs to guess which unseen movies a user will like based on the viewing habits of everyone else. Mathematicians model this guessing task using a giant grid called a matrix. The rows represent users and the columns represent movies. Because people have only rated a few items, the grid is mostly empty. The goal is to fill in the missing entries well enough to make a good recommendation. This process relies on a concept called matrix completion. Human tastes are not entirely random. If a user likes one science fiction action movie, they will probably like another. This means the massive grid of data can be compressed into a smaller set of underlying categories or preferences. The 2016 quantum algorithm by Kerenidis and Prakash looked unbeatable because it claimed to sample from this matrix exponentially faster than any known classical method. Instead of generating the complete, time-consuming grid, the algorithm delivered a simpler, effective recommendation for a specific user. This was significant, marking a rare instance where a quantum algorithm was applied to a big data challenge, moving beyond purely theoretical "toy problems." The result fueled investor optimism that quantum computing was on the cusp of optimizing global commerce.
During the spring semester of 2017, Tang took an introductory course on quantum information science. The class was taught by Scott Aaronson, who is one of the most prominent theoretical computer scientists in the world. Aaronson quickly noticed that Tang was an unusually talented student. When she approached him to ask if he would supervise her senior honors thesis, he agreed. Aaronson gave Tang a specific homework assignment. He wanted her to prove that no fast classical algorithm could ever match the speed of the Kerenidis and Prakash quantum algorithm. He wanted her to confirm that the quantum speedup was mathematically absolute. The assignment backfired in the best way possible. Tang spent weeks trying to prove that a fast classical method was impossible. She hit a brick wall. She felt utterly blocked. Her frustration mounted because she could not find a mathematical reason why a normal computer could not perform the task. It was after repeated failures that it hit her. She started looking at the problem from the opposite direction. She realized she might be able to build a classical algorithm that copied the quantum trick. The key idea that unlocked the problem involved hidden assumptions about how a computer accesses data. The Kerenidis and Prakash quantum algorithm relied on a massive assumption. It assumed the giant matrix of user data was already loaded into a quantum state using a theoretical piece of hardware called quantum random access memory. This is known in the field as a state preparation assumption. It essentially gives the quantum computer a magical fast pass to read the entire dataset instantly. Tang built a parallel assumption for the classical world. She reasoned that if the quantum computer gets a fast pass, the classical computer should get one too. She defined a classical data structure that allowed for extremely fast probability sampling. This is known as L2 norm sampling access. Once she gave her classical algorithm this equivalent starting advantage, she used techniques from a 2004 paper by Frieze, Kannan, and Vempala to approximate the matrix. Her classical algorithm did the unthinkable: it ran in polylogarithmic time. This meant its speed scaled with the logarithm of the data size, just like the quantum algorithm. The legendary exponential speedup was an illusion caused by generous data loading rules. When Tang realized what she had done, she was hesitant to tell her advisor. She sent Aaronson an email saying she thought she had a fast classical algorithm, but was not entirely sure. Aaronson was highly skeptical. He believed a classical algorithm would need to look at the whole matrix, which would take too much time. Tang spent months refining the proof. Finally, Aaronson realized she was right. To be absolutely certain, he arranged for her to present the findings at the Simons Institute workshop in Berkeley. Tang stood before the experts and laid out her proof. When the four hour session ended, the experts agreed. Tang had survived the scrutiny.
How the community decides something is real always begins with informal consensus and then moves to formal peer review. Tang posted her paper online in July 2018 titled A quantum inspired classical algorithm for recommendation systems. Internet was flooded with dramatic headlines suggesting that quantum computing was now useless, with some articles even claiming it was completely finished. Recommendation systems were supposed to be the bridge between abstract quantum physics and commercial profitability. Now, an eighteen year old undergraduate had proven that a regular computer could theoretically achieve the same scaling performance if the data was prepared correctly. Tang and Aaronson repeatedly clarified that their algorithm didn't mean quantum computing was a bust. The scope of the algorithm was actually pretty specific. Their paper essentially showed that a lot of those claimed speedups for machine learning tasks with regular data might just disappear when you make a proper, fair comparison. Tang's work sets a new limit for what's possible in computation down the road. Her math basically shows that getting a true "quantum edge" in machine learning, especially with regular, classical data, is way tougher than we thought. The core issue is the data loading bottleneck. If a task needs a ton of classical data shoved into a quantum computer, the time you spend prepping that data often just eats up any speed boost you'd get from the quantum calculation itself. Tang thinks quantum computers are a game-changer, especially for simulating physical systems. That's where the data follows the rules of physics, which is the sweet spot for these machines. Take the example of simulating complex chemical reactions. A prime example is the research on nitrogenases—these enzymes are key for 'fixing' nitrogen, which we need to make agricultural fertilizer. Right now, making that fertilizer is a massive energy hog due to the super high heat and pressure required, burning through a huge chunk of global energy. But if we can simulate the exact quantum states of those molecules, quantum computers could give engineers the breakthrough they need to design way, way more efficient chemical processes.
After her undergraduate studies, Tang moved to University of Washington where she began her doctoral studies under the supervision of James Lee. She systematically dequantized a whole suite of linear algebra and machine learning algorithms. She published papers dismantling the claimed quantum exponential speedups for principal component analysis. She dequantized algorithms for supervised clustering. She took apart quantum approaches to low rank stochastic regression. In 2023, she completed her doctoral dissertation titled Quantum machine learning without any quantum. In this massive body of work, she observed that the space of quantum machine learning algorithms splits into two distinct classes. If the input data is sparse, the algorithms remain uniquely powerful. If the input data relies on quantum accessible data structures for dense low rank matrices, the algorithms can be matched by classical machines. She now studies Hamiltonians and Gibbs states. A Hamiltonian is a mathematical operator that describes the total energy of a quantum system. A Gibbs state describes a system at thermal equilibrium. In 2024, she coauthored a major paper providing the first polynomial time algorithm for learning a local quantum Hamiltonian at any temperature, given copies of its Gibbs state. This work solves major open problems in physics and computing. The data is no longer a spreadsheet of movie preferences. It is a physical quantum object.
In 2019, Forbes magazine named her to their Thirty Under Thirty list in the Science category. She was only eighteen years old at the time. She presented her work at the Symposium on Theory of Computing, a highly prestigious top tier conference. She secured a plenary talk and won the best student paper award at the Quantum Information Processing conference in 2020. Her ultimate validation arrived in 2025. The Breakthrough Prize organization awarded Tang the Maryam Mirzakhani New Frontiers Prize. The Breakthrough Prizes are heavily funded by Silicon Valley billionaires and are widely referred to as the Oscars of Science. The organization hosts a massive televised gala at the Barker Hangar in Santa Monica, California. The prize awards fifty thousand dollars to early career women who have made exceptional contributions to mathematics. Actors Drew Barrymore and Ke Huy Quan presented the award to Tang and two other mathematicians during the Hollywood ceremony. Tang completed her doctoral degree at the University of Washington in 2023. She is currently serving as a Miller Postdoctoral Fellow at the University of California, Berkeley, where she is hosted by Umesh Vazirani. In the fall of 2026, she will join the faculty of Princeton University as an assistant professor in the computer science department. At Princeton, she will be directly affiliated with the Princeton Quantum Initiative. Her near-term research questions remain focused on the boundary between physics and computation. She is currently investigating how to efficiently learn the parameters of unknown quantum systems. She is determining when a machine can find a product state with optimal fidelity to an unknown quantum state, given limited copies. These highly technical queries all connect back to a single guiding question that has driven her entire career. What tasks can be performed efficiently in a universe governed by quantum mechanics? The long-term stakes of her work are monumental. By systematically stripping away the false hopes of quantum machine learning on classical data, she has forced the sector to hunt for real, undeniable quantum advantages. If her perspective holds true, the next decade of computing will look very different than what we thought.