Dequantization: When Classical Computers Catch Up
A plot twist that helped everyone
In 2016 and 2017, a quantum algorithm for recommendation systems by Iordanis Kerenidis and Anupam Prakash was widely viewed as one of the strongest candidates for an exponential quantum advantage in machine learning. In 2018, Ewin Tang published "A quantum-inspired classical algorithm for recommendation systems," which gave a classical method running in time polynomial in the rank of the matrix and logarithmic in its size. The paper concludes that the quantum algorithm does not in fact give an exponential speedup over classical algorithms. Tang's classical algorithm is only polynomially slower than the quantum one.
This process is called dequantization, and algorithms born from it are called quantum-inspired. The word "inspired" is fair: the classical idea came from studying how the quantum one worked.
What made it possible: the input assumption
The key is what the quantum algorithm assumes about its input. The quantum method assumes a data structure that lets you prepare quantum states from stored data efficiently. Tang asked: what if a classical computer gets a comparable kind of access, namely the ability to sample entries with probability proportional to their squared size? Under that fair comparison, a classical computer can do a surprising amount.
A follow up paper by Tang, titled "Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions" (published in Physical Review Letters in 2021), applied the same lens to quantum PCA and to nearest centroid clustering. It gave classical analogues that are only polynomially slower and argued that the exponential edge came from the state preparation assumptions rather than from quantum computation itself.
It grew into a framework
Later work by Chia, Gilyen, Li, Lin, Tang and Wang built a sampling based framework mirroring the quantum singular value transformation, and recovered and often improved dequantization results for recommendation systems, principal component analysis, supervised clustering, support vector machines, low rank regression and semidefinite programs. The authors argue that in the corresponding data structure input model, the quantum approach does not yield exponential speedups. That is their interpretation under a specific input model, and the field continues to refine it.
What dequantization does not say
- It does not say quantum computers cannot help. The classical algorithms are still slower in some regimes, and they depend on strong assumptions such as low rank data.
- It does not touch the algorithms where there is no known classical shortcut, such as Shor's factoring algorithm or simulating quantum systems.
- It does not claim every quantum learning algorithm will be dequantized. Each case has to be examined.
- Polynomial gaps can still matter in practice. A quadratic or better speedup on a very large problem could be valuable once hardware is mature.
The lesson: what to look for in a claimed speedup
Dequantization gave the community a simple checklist for any exponential claim in machine learning:
- What input access does the quantum algorithm assume?
- Would a classical algorithm with equivalent sampling access be fast too?
- Is the data low rank or otherwise structured in a way that makes classical shortcuts easy?
- Does the problem have a hardness argument, not just a lack of known classical methods?
Where the answers hold up, the evidence for a true advantage is much stronger. Famous examples where advantages are argued to be on firmer ground include learning tasks built on the hardness of the discrete logarithm problem and learning from quantum experiments. See quantum kernels and the power of data.
Why this is a positive story
A healthy science corrects itself. Because of dequantization, we have better classical algorithms for large low rank problems, which is a gift to practitioners today, and we have a sharper map of where quantum advantage must live. That is also how cryptography, complexity theory and numerical computing improved: every proposed speedup was stress tested by clever rivals. The quantum side is stronger for it. Researchers now direct effort at problems with strong evidence, such as simulating nature, rather than at tasks where a classical sampler is a close competitor.
It also teaches a media literacy habit. When you read that a quantum machine will transform AI, check whether the claim survived an attempt to beat it with classical tricks. For the broader scoring, see the scorecard and supremacy and advantage. This is education, not financial advice.
Sources and further reading
- arXiv: Ewin Tang, A quantum-inspired classical algorithm for recommendation systems
- arXiv: Ewin Tang, Quantum PCA only achieves an exponential speedup because of its state preparation assumptions
- arXiv 1910.06151: Sampling based sublinear low rank matrix arithmetic framework for dequantizing quantum machine learning
- Quanta Magazine: The Joy of Why, the true promise of quantum computing
Reported as of 2026-10-09. Research moves fast, so check the papers and company announcements. Educational only, not financial advice. The QNT memecoin is an independent community project and is not linked to Quantinuum Ltd or any lab or government.
Frequently asked questions
What is dequantization?
Finding a classical algorithm that matches a claimed quantum speedup, usually by giving the classical computer a comparable kind of data access.
Did Ewin Tang prove quantum computers are useless for AI?
No. Tang showed one prominent exponential speedup claim, for recommendation systems, was not exponential. Other quantum advantages are untouched.
What does quantum-inspired mean?
A classical algorithm whose design was derived from studying a quantum algorithm. It runs on normal computers.
Is this financial advice?
No. It is an educational explainer.
Keep reading
- The Data Loading Problem: Quantum Computing's Fine Print for AI
Why getting big classical data into a quantum computer can erase a speedup, and what Scott Aaronson's fine print means for quantum machine learning. - Quantum Machine Learning Explained
What is quantum machine learning? A careful, plain English look at how quantum computers might help AI, what is proven, and what is still hype. - Quantum Kernels and the Power of Data: Where Advantage Might Be Real
A tour of quantum kernel methods, the Huang et al. power of data result, the provable Liu-Arunachalam-Temme speedup, and learning from quantum experiments. - Quantum AI Scorecard: What Is Proven and What Is Promised
An honest scorecard of quantum AI claims in 2026: proven results, promising research, open questions and hype to ignore.
All Quantum industry, people and AI guides | Back to top | Search the site
Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary