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.
-
Airbus and Mercedes take the G-Class to the skies: the ACH145 helicopter priced at R$ 78 million debuts in São Paulo, unit goes to Brazilian, AMG cabin, 5-blade rotor, and a 2-year wait.
-
New material could change everything: it is the thickness of an atom, 200 times stronger than steel, and 100,000 times thinner than a human hair.
-
A new study published in Nature reveals that the SLIT3 protein can increase calorie burning by activating brown fat in the body, functioning as a kind of “biological switch.”
-
New signals detected by NASA suggest that the Moon may hide accessible underground cavities, after data from Mini-RF indicated a conduit over 60 meters beneath a lunar pit.
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.