Portuguese 
English 
Spanish 
6 min of reading 
0 comments 
At 18, Texas Student Challenges One of the Greatest Certainties of Quantum Computing and Shows That Ordinary Computers Can Solve the Same Problem.
Ewin Tang was not an ordinary freshman. She had skipped four grades, taken college courses at 10, and arrived on campus with a 4.0 GPA — the highest possible grade in every criterion. The daughter of two biotechnology researchers, she had already co-authored scientific papers on optical imaging in a nanotechnology lab before finishing high school. In 2017, during her junior year, she entered Scott Aaronson’s quantum computing class.
The Man Who Defined the Limits of the Impossible
Scott Aaronson is not just any quantum computing professor. He is one of the most cited researchers in the field, author of the reference book Quantum Computing Since Democritus, and an expert on a specific question: defining what quantum computers can do that classical ones could never achieve. His work is, in part, about constructing the frontiers of computational impossibility.
When he recognized Tang’s talent, he offered her a list of problems for independent research — PhD-level projects proposed for a 17-year-old undergraduate.
-
While the world looks at oil, the war with Iran is already disrupting helium supply from Qatar, affecting car and iPhone chips, threatening AI expansion, and putting pressure on aluminum packaging at the highest value in four years.
-
Global warming will expose a treasure hidden under the ice of Antarctica and may spark an international dispute over gold and valuable minerals.
-
A street vendor from Praia Grande built a robot made of scrap from scooters and washing machines that pulls his popcorn cart on the beach, emits sounds, and interacts with customers, becoming an attraction on the coast of São Paulo.
-
The specifications of the Xiaomi 18 Pro Max have been leaked, and the highlight is a dual 200 MP camera with a new 22-nanometer technology that promises to consume less energy and capture details in shadows and bright areas using LOFIC HDR.
Tang chose what seemed the most accessible from the list. It was a problem called the recommendation problem.
The Algorithm That Seemed Unbeatable
In 2016, two renowned researchers — Iordanis Kerenidis from Paris Diderot University and Anupam Prakash — published a quantum algorithm that shook the field.
The problem they solved is simple to state: how does Netflix decide which series to recommend? How does Amazon know which product to show? The answer involves processing huge matrices — tables with millions of users in rows and millions of products in columns — and identifying preference patterns without needing to read each cell individually.
Classical algorithms did this in linear time relative to the size of the matrix. For a table with one hundred million users, the processing time grew proportionally.
Kerenidis and Prakash’s algorithm ran in polylogarithmic time — it grew with the logarithm of the size, not with the size itself. In practice, an exponential speedup. Classical computers, according to the consensus at the time, would never come close to this performance.
It was considered one of the most solid examples of genuine quantum advantage — not theoretical, not restricted to artificial problems, but applicable to the real world.
The Mission: Prove That It’s Impossible
When Aaronson proposed the problem to Tang in 2017, the question was not, “Can you solve this classically?”.
The question was the opposite. He wanted her to prove that no classical algorithm could come close. Mathematically confirm that Kerenidis and Prakash’s quantum advantage was real and insurmountable. Close the issue for good.
“That seemed like an important ‘t’ to cross to complete this story,” Aaronson later said, explaining why he had framed the task that way. He genuinely believed that no classical algorithm existed.
Tang began working on it in the fall of 2017, as her undergraduate thesis project.
Months Trying to Prove the Impossible
For several months, Tang worked to build the proof that Aaronson expected.
She tried to show that any classical algorithm would require too many queries to the matrix to be competitive. She sought the lower bound — the mathematical floor below which no classical method could descend.
She found none. And while she couldn’t find it, she began to suspect why. “I started to believe there was a fast classical algorithm,” she later said. “But I couldn’t prove it because Scott seemed to think there wasn’t one — and he was the authority.”
This tension — the student’s intuition against the certainty of the advisor who had devoted his career to the subject — defines what would come next.
Throughout the spring of 2018, Tang did not find the proof of the impossible. She found the opposite: a classical algorithm that solved the recommendation problem in polylogarithmic time, equivalent to that of the quantum computer.
The central idea was to replace the quantum sampling techniques used by Kerenidis and Prakash with classical sampling techniques that had analogous mathematical properties. The algorithm did not need to reconstruct the entire matrix — as previous classical methods did — but rather sample directly from the most relevant entries. The result was exponentially faster than any previous classical method.
Four Hours in Front of the Original Authors
Aaronson was nervous. Not about Tang — but about the possibility that the result was wrong. An incorrect proof published as the first major work of a young researcher would be a career disaster. He needed external verification before anything else.
In June 2018, Aaronson was confirmed to participate in a quantum computing workshop at the University of California in Berkeley. Several of the biggest names in the field would be there — including Kerenidis and Prakash, the very authors of the quantum algorithm that Tang had just challenged.
Aaronson invited Tang to present the results informally in the days following the official event.
On June 18 and 19, 2018, Tang gave two lectures. For four hours, the attending researchers asked questions, probed the logic, searched for flaws.
Kerenidis, one of the authors of the original algorithm, was in the room. At the end of the four hours, the consensus was clear: Tang’s algorithm appeared correct. “I didn’t know Ewin was 18,” Kerenidis said afterward. “Certainly, I didn’t realize that from the talk. To me, it was someone giving a very mature presentation.”
What “Dequantizing” an Algorithm Means
Tang’s result gained a technical name in the field: dequantization. The process consists of taking a quantum algorithm — which relies on state superposition, interference, and probabilistic measurements — and demonstrating that a classical algorithm can replicate its performance using equivalent sampling techniques.
This does not mean that quantum computers are useless. Aaronson was explicit about this: breaking cryptography, simulating chemical and physical systems, and various classes of optimization problems remain areas where the quantum advantage remains intact.
What Tang demonstrated is that the recommendation algorithm, specifically, was not a valid example of quantum advantage. The frontier of impossibility was poorly drawn — and she had redrawn it.
STOC 2019 and the Beginning of a New Line of Research
Tang’s paper, titled A Quantum-inspired Classical Algorithm for Recommendation Systems, was published in July 2018 in the ECCC repository and accepted for presentation at the ACM Symposium on Theory of Computing — STOC 2019, considered one of the most selective conferences on computer theory in the world.
At QIP 2020 — the largest annual quantum information conference — she was invited for a plenary talk and received the best student paper award.
The impact went beyond the original problem. The work opened an entire line of research: the systematic search for other quantum machine learning algorithms that could be dequantized. Tang and collaborators applied the same approach to principal component analysis, low-rank stochastic regression, and clustering — fundamental problems in data science.
Tang graduated with a degree in pure mathematics and computer science with a 4.0 GPA, was named a Distinguished Undergraduate by UT Austin, and in 2019 made it to the Forbes 30 Under 30 list in the science category.
In 2023, she completed her PhD at the University of Washington. She is now a researcher at the University of California in Berkeley, where she continues to develop the interface between classical and quantum algorithms.
In 2025, she received the Maryam Mirzakhani New Frontiers Prize — one of the distinctions of the Breakthrough Prize, considered the Nobel of mathematics — for “developing classical analogs of quantum algorithms for machine learning and linear algebra, and for advances in quantum machine learning on quantum data.”
The award came seven years after an 18-year-old student had tried to prove that the impossible was impossible — and discovered that it was not.
-
-
2 pessoas reagiram a isso.