What Quantum Does Not Do

By the end of this session you will be able to:

• Name the problem families where a quantum computer is believed to beat every classical algorithm, and say which size of speedup each one gets.
• Explain why a superposition over 2^n strings does not let you check 2^n answers, using the fact that a measurement hands back n bits.
• Screen any proposed quantum application with two questions about its input and its output.

Everything here runs on your laptop with Python and NumPy. Qiskit 2.5 arrives later in this phase.

The list of real speedups is short

Three families, and that is nearly all of it.

Simulating quantum systems. Molecules, materials, lattice field theories. Classical cost grows exponentially in the number of interacting particles; quantum cost does not. This is what quantum computing was proposed for in 1982 and it is still the strongest case.

Period finding. Shor's algorithm factors integers and computes discrete logarithms in polynomial time, superpolynomially faster than anything known classically. RSA, Diffie-Hellman and elliptic curve cryptography all sit on those two problems, which is why this one gets the headlines.

Unstructured search and what is built on it. Grover's algorithm finds a marked item among N candidates in about the square root of N steps instead of N. Amplitude estimation gives Monte Carlo estimation a similar quadratic improvement. Quadratic, not exponential, and that difference is the whole point of this session.

"Believed" is doing real work above. Nobody has proved factoring is hard classically, or that quantum computers are strictly more capable than classical ones. Each item is a gap between the best known classical algorithm and a known quantum one, not a theorem. Everything outside those three families is a quadratic speedup in disguise, a heuristic with no proof of anything, or a claim that fell apart when someone looked at it carefully.

A superposition is not a parallel search

The pop-science line is that n qubits hold 2^n values at once, so a quantum computer tries every answer and returns the right one. The first half is roughly true. The second is where it breaks.

An n-qubit state is 2^n complex amplitudes. Measuring it returns exactly n classical bits, one string, chosen at random with probability equal to the squared magnitude of that string's amplitude. You do not get the amplitude vector. You get one sample from it, and the state is gone afterwards. Run this:

import numpy as np
 
n = 20
state = np.full(2**n, 1 / np.sqrt(2**n))
probs = np.abs(state) ** 2
 
rng = np.random.default_rng(0)
outcome = rng.choice(2**n, p=probs)
 
print("amplitudes stored:", state.size)
print("bits returned    :", n)
print("outcome          :", format(outcome, "020b"))

amplitudes stored: 1048576
bits returned    : 20
outcome          : 10100011000011111110

That is the equal superposition over a million strings, the state people mean by "all answers at once". Measuring it is indistinguishable from a random number generator.

So the useful work in a quantum algorithm is not the superposition. It is what happens between creating it and measuring it: arranging the amplitudes so wrong answers acquire opposite signs and cancel, leaving probability piled onto the right one. That is interference, and it needs mathematical structure in the problem to hook into. Factoring has periodic structure. A pile of unrelated candidate answers has none, which is why searching it stays hard.

This is not a gap waiting to be closed. Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum algorithm needs on the order of the square root of N queries to find a marked item among N with no structure to exploit. Grover hits that bound exactly, so no future algorithm brute-forces an NP-complete problem exponentially faster.

Two questions that kill most applications

How does the data get in? Loading N classical numbers into a quantum state takes on the order of N operations. If your algorithm must look at every row of a dataset to start, you have already paid the classical cost before the quantum part begins. Proposals that dodge this assume a component called QRAM that nobody has built at scale.

How does the answer get out? You get n bits per shot. An algorithm ending in a state that encodes a million-element solution vector has not handed you that vector. It has handed you something you can sample from, and reading it all out costs at least as much as computing it classically would have.

Those two questions are how a class of quantum machine learning results got dequantized. In 2018 Ewin Tang showed the quantum recommendation systems algorithm had no exponential advantage: the sampling assumptions that make the quantum version fast make a classical version fast too.

Here is the arithmetic on the one everyone reaches for, database search:

import math
 
N = 10**12
iterations = math.floor((math.pi / 4) * math.sqrt(N))
seconds_per_iteration = 1e-6
 
quantum_seconds = iterations * seconds_per_iteration
classical_seconds = 1e-7
 
print("Grover iterations :", iterations)
print("Grover seconds    :", round(quantum_seconds, 3))
print("Lookup seconds    :", classical_seconds)
print("Grover slower by  :", round(quantum_seconds / classical_seconds), "x")

Grover iterations : 785398
Grover seconds    : 0.785
Lookup seconds    : 1e-07
Grover slower by  : 7853980 x

A microsecond per iteration is generous by orders of magnitude for 2026 hardware, and Grover still loses to a hash table by seven million times. It loses structurally, not on speed: a hash table is structure, and Grover throws it away. Grover does not search a database. It searches the inputs of a function you supply as a reversible circuit.

What the hardware can actually do this month

IBM's available processors today are Nighthawk at 120 qubits and Heron r3 at 156: physical, noisy qubits with no error correction in the production stack, so circuit depth runs out long before qubit count does. The free Open Plan gives you 10 minutes of QPU time per 28-day rolling window, on a shared queue.

Set that against Craig Gidney's 2025 estimate for factoring a 2048-bit RSA key (arXiv:2505.15917): under a million noisy qubits running for under a week, a large improvement on his own 2019 figure of 20 million qubits for eight hours. The distance from 156 to 1,000,000 is the state of the field, and IBM's own advantage framework paper (arXiv:2506.20658) says nobody has cleared the validation bar yet.

Try it

Save the Grover script as grover_crossover.py. Replace the hash-table lookup with a classical linear scan costing N * 1e-9 seconds, the fair comparison, because Grover also evaluates a predicate on candidates rather than jumping straight to the answer.

1. Find the smallest N at which Grover's wall clock beats the linear scan. Solve it on paper first, then confirm by looping N over powers of ten.
2. Re-run with seconds_per_iteration = 1e-3, closer to a deep circuit on real hardware today, and find the new crossover.
3. Go back to the hash-table comparison and work out why no crossover exists there at any N.

You are done when you can state both crossovers to two significant figures and say in one sentence why the hash-table version has none.

Common mistakes

• Saying a quantum computer "tries all answers in parallel". It holds 2^n amplitudes and returns n bits. Every speedup comes from interference cancelling wrong answers before you measure, which needs structure the problem already has.
• Assuming quantum breaks all encryption. Shor breaks RSA, Diffie-Hellman and elliptic curve cryptography, public-key schemes built on the two problems it solves. AES-256 and SHA-256 are not, and Grover at best halves their effective key strength, in a long computation that cannot be parallelized away.
• Expecting a speedup on machine learning or big data. Both screening questions land badly: the input is large so loading dominates, the output is large so readout dominates.
• Reading qubit counts as progress toward Shor. 156 physical qubits is not 156 logical qubits, and the ratio is large. What limits you today is coherence and gate error, not chip width.
• Treating a benchmark as an application. Random circuit sampling and similar demonstrations are chosen because they are hard classically, not because anyone wants the output.

Where this goes next

You now know what interference has to do and why nothing works without it. The next session, Just Enough Complex Numbers, gives you the math that makes cancellation possible: magnitude and phase, and why squaring a magnitude is where probability comes from.