Article 5 of 9 — Foundations of Quantum Computing
The promise of quantum computing rests entirely on algorithms — specific recipes that solve certain problems faster than any classical computer could. But the popular story badly overstates the case. Quantum computers don't speed up "computing" in general; they speed up a handful of particular problems, by wildly different amounts, and the most famous speed-ups require machines far beyond what exists today. This article sorts out where the advantage is genuinely revolutionary, where it's merely useful, and where it disappears — which is the foundation for judging every application and investment claim in the articles that follow.
The basics walk through the headline algorithms and what "quantum advantage" means. Going Deeper examines the crucial differences between exponential, quadratic, and no speed-up — and the gap between a demonstration and a useful result.
The basics: the headline algorithms
Shor's algorithm is the famous one. It can factor very large numbers — break them into their prime components — exponentially faster than the best known classical methods. That sounds abstract, but it's enormous: the security of much of today's internet encryption rests on factoring being hard for classical computers (Article 6 follows this thread). Shor's algorithm is the clearest example of a genuine, dramatic quantum speed-up.
Grover's algorithm searches an unstructured list far faster than checking every entry one by one. Crucially, though, its speed-up is quadratic, not exponential — roughly, it cuts the work to the square root of the classical amount. For a list of a trillion items, that's a million-fold improvement, which sounds huge but is far more modest than Shor's exponential leap, and is often overstated in popular accounts.
Quantum simulation may be the most natural and important use of all. Quantum computers are themselves quantum systems, so they're well suited to simulating other quantum systems — molecules, materials, chemical reactions — that classical computers struggle to model. This was the original motivation for quantum computing (the physicist Richard Feynman's idea), and many researchers consider it the most promising near-to-medium-term payoff.
The basics: "quantum advantage" and "supremacy"
You'll hear two phrases constantly. Quantum advantage (sometimes quantum supremacy) means a quantum computer performing some task that no classical computer could do in any reasonable time. It's a real scientific milestone — but it comes with a heavy caveat: the tasks chosen to demonstrate it are often deliberately contrived to favour the quantum machine, with no practical use. Demonstrating advantage on a made-up benchmark is not the same as doing something useful, and the two are routinely conflated in headlines.
The basics: the speed-up is problem-specific
The single most important point: quantum speed-ups apply only to specific problems with the right mathematical structure. For the vast majority of computing tasks, a quantum computer offers no advantage at all — it would be as slow as, or slower than, a classical machine. Quantum computing is a sharp tool for a few problems, not a general accelerator. Any claim that it will "make everything faster" is simply wrong.
Going deeper: exponential, quadratic, or nothing
For readers who want the real picture, the size and fragility of the speed-up are everything.
Exponential vs. quadratic is a chasm. An exponential speed-up (like Shor's) turns problems that would take longer than the age of the universe into ones that take hours — that's transformative. A quadratic speed-up (like Grover's) is useful but far less dramatic, and it can be partly or wholly eaten by the overhead of running on error-corrected quantum hardware. Several touted "quantum optimization" speed-ups are quadratic at best, which is why sober analysts are cautious about them even when they're real.
The resource gap is brutal. Shor's algorithm could break current encryption in principle, but doing so for real-world key sizes would require a large, fault-tolerant machine with vastly more high-quality qubits than anyone has built — by orders of magnitude, given the error-correction overhead from Article 4. The algorithm existing is not the same as the machine to run it existing. This gap between theory and hardware is the most important caveat in the whole field.
Classical computers fight back. "Quantum advantage" claims have repeatedly been narrowed or overturned when researchers found cleverer classical methods to do the same task, or better classical simulations of the quantum machine. The classical baseline is a moving target, not a fixed one — so an advantage demonstrated today can erode tomorrow. This back-and-forth is healthy science, but it means single announcements should be read with caution.
Demonstration ≠ usefulness. A circuit that shows a speed-up on a toy problem is a long way from software that delivers value on a real one. Bridging that gap requires not just better hardware but algorithms whose advantage survives realistic problem sizes, data-loading costs, and error-correction overhead — none of which are guaranteed.
The takeaway
Quantum algorithms deliver speed-ups only on specific, structured problems — and the size varies enormously. Shor's factoring is an exponential, transformative speed-up (but needs hardware far beyond today's); Grover's search is a more modest quadratic one (and easily overstated); quantum simulation of molecules and materials may be the most promising practical use. "Quantum advantage" is a real milestone but is usually shown on contrived, useless benchmarks. For most computing, quantum offers nothing — it's a specialized tool, and the gap between an algorithm on paper and a useful result on real hardware is large.
What people commonly get wrong
- "Quantum speeds up everything." It helps only specific structured problems; most tasks get no benefit.
- "All quantum speed-ups are exponential." Many, like Grover's, are merely quadratic — useful but far less dramatic, and overhead can erode them.
- "Shor's algorithm means encryption is broken now." The algorithm exists; the large fault-tolerant machine to run it at real scale does not.
- "A supremacy demo means quantum computers are useful." The benchmark tasks are often contrived and have no practical value.
- "A demonstrated advantage is permanent." Better classical methods have repeatedly narrowed or overturned such claims.
This article is educational and deliberately simplified. It is not technical, financial, or professional advice.
Sources for further reading: standard treatments of Shor's and Grover's algorithms and quantum simulation, including Nielsen & Chuang; peer-reviewed literature and reputable technology press on quantum-advantage demonstrations and their classical rebuttals.
Next in the series: Article 6 — Quantum and Cryptography: the most concrete near-term stake, from the encryption threat to the global migration already underway.
