Where quantum helps — and where it doesn't

Quantum computers are sometimes described as "exponentially faster computers". They are not. For most tasks they would be slower than the classical machines you already use. What they offer is a different model of computation that is dramatically better for some problems. This lesson gives you a map, so that you can judge any claim you read.

Measuring speed-ups

We compare algorithms by how their running time grows with the input size $n$ — for example the number of digits in a number to be factored, or the number of items to search.

An exponential speed-up turns something like $2^n$ steps into something like $n^3$ steps. For large $n$ this is the difference between "impossible" and "routine".
A polynomial speed-up turns, say, $N$ steps into $\sqrt{N}$ steps (a quadratic speed-up). Useful, but much more modest.
No speed-up: the best quantum algorithm is no better (in scaling) than the best classical one.

The map

Problem	Best known quantum	Best known classical	Speed-up	Status
Factoring integers, discrete logarithms	Shor's algorithm, polynomial time	Number field sieve, sub-exponential time	Super-polynomial	Proven algorithm; needs large fault-tolerant machines
Simulating quantum physics and chemistry	Polynomial time for many systems (Lloyd 1996)	Exponential in general	Exponential for many systems	Leading candidate for early practical value
Unstructured search over $N$ items	Grover, about $\sqrt{N}$ queries	$N$ queries	Quadratic, and provably optimal	Proven; practical value limited by overheads
NP-complete problems (e.g. SAT, travelling salesperson)	Grover-style, still exponential	Exponential	At most quadratic, as far as we know	No exponential speed-up expected
Adding numbers, sorting, word processing	—	Already fast	None	Use a classical computer

Two entries deserve a closer look.

Factoring: the famous exponential gap

The security of widely used public-key cryptography such as RSA rests on factoring large numbers being hard. The best known classical algorithm, the general number field sieve, takes time that grows faster than any polynomial in the number of digits. Shor's algorithm runs in polynomial time on a quantum computer. That is why governments are already migrating to post-quantum cryptography — even though no existing quantum computer is anywhere near large or reliable enough to break RSA-2048.

Search: a quadratic speed-up that is provably the best possible

Grover's algorithm finds a marked item among $N$ with about $\frac{\pi}{4}\sqrt{N}$ queries, where a classical algorithm needs about $N/2$ on average. In 1997 Bennett, Bernstein, Brassard and Vazirani proved that no quantum algorithm can do better than order $\sqrt{N}$ for unstructured search. Consequently, quantum computers are not expected to solve NP-complete problems in polynomial time: brute-force search over $2^n$ candidates speeds up to about $2^{n/2}$ — still exponential.

Knowledge check

Are quantum computers expected to solve NP-complete problems (like large travelling-salesperson instances) in polynomial time?

Yes — Grover's algorithm turns exponential search into polynomial timeYes — Shor's algorithm works for any NP problemNot as far as we know — the best known general speed-up is quadratic, which leaves the running time exponentialNo — quantum computers are slower than classical ones for every problem

Why "quadratic" often isn't enough

A quadratic speed-up sounds great on paper: $10^{12}$ steps become $10^6$ . But real quantum computers pay two big overheads:

Slow operations. A classical processor performs billions of simple operations per second. An error-corrected quantum computer is expected to perform logical operations far more slowly — estimates are many orders of magnitude slower per operation.
Error-correction overhead. Each reliable "logical" qubit is expected to require hundreds to thousands of physical qubits.

Babbush and colleagues (2021) estimated that with realistic assumptions, quadratic speed-ups on early fault-tolerant machines would need problem instances so large that the quantum computer would run for an impractically long time before overtaking a classical computer. Hoefler, Häner and Troyer (2023) reached a similar conclusion and recommended focusing on problems with super-quadratic speed-ups and small input/output — such as chemistry and materials simulation.

The data bottleneck

Many proposed applications — especially in machine learning — assume large classical datasets can be loaded into quantum amplitudes cheaply. In general they cannot: loading $N$ arbitrary numbers takes time that grows at least in proportion to $N$ , which can wipe out a speed-up that was supposed to make the computation sub-linear in $N$ . Similarly, reading out a full $2^n$ -amplitude answer would take exponentially many measurements.

Aaronson's short essay Read the fine print (2015) lists these caveats for a famous algorithm (HHL) for linear systems of equations. We will revisit them carefully when we study quantum machine learning.

Knowledge check

What is the "data-loading problem" in quantum algorithms?

Quantum computers cannot store numbers larger than 1Loading N arbitrary classical values into a quantum state generally takes time at least proportional to N, which can cancel a claimed sub-linear speed-upQuantum memory is always larger than classical memoryMeasurement returns all 2ⁿ amplitudes, which is too much data to store

Where does that leave us?

Most promising: simulating quantum systems (chemistry, materials, condensed-matter physics), and cryptanalysis (Shor) once large fault-tolerant machines exist.
Plausible but unproven: certain optimisation, sampling and machine-learning tasks — an active research area with many open questions.
Not expected: general-purpose speed-ups for everyday computing, or efficient solutions to NP-complete problems.

Keep this map in mind. When you meet a new claim — in a paper, a press release or a pitch deck — ask: What is the speed-up? Over which classical algorithm? Proven or conjectured? Does it survive data loading, read-out and error-correction overheads?