Quantum algorithms: where the speedups actually are

The earlier lessons built the machine: qubits that interfere, hardware that hosts them, codes that make them reliable. The final question is what the machine is for, and here a single test sorts hype from substance:

Does the problem have structure that interference can exploit, and is the speedup large enough to survive the overhead?

Both halves matter. Interference (amplitudes canceling and reinforcing) is the only mechanism a quantum computer has; problems without exploitable structure get no speedup at all. And because logical qubits cost roughly a thousand physical ones, and logical gates run slower than classical transistors by orders of magnitude, a small theoretical speedup can be eaten entirely by the machinery that produces it.

The rest of this lesson applies that test to the three algorithm families that dominate the field, then to the application areas most often claimed in headlines: cryptography, chemistry, optimization, and machine learning. The results differ far more than the marketing suggests.

Shor's algorithm (1994) factors large integers, and its existence is the reason quantum computing left academia. RSA encryption rests on factoring being infeasible: the best classical algorithms scale sub-exponentially but super-polynomially in the number of digits. Shor factors in polynomial time, turning a computation measured in ages-of-the-universe into one measured in hours, for a large enough machine.

The structure it exploits: factoring reduces to period finding. If you compute powers $a^1, a^2, a^3, \dots \pmod{N}$, the results repeat with some period $r$, and knowing $r$ cracks $N$ open. Classically, finding $r$ means hunting through exponentially many values. Shor instead prepares a superposition over all exponents at once and applies the quantum Fourier transform, which makes every amplitude that disagrees with the true period cancel, and every amplitude consistent with it reinforce. The measurement then yields the period with high probability.

This is interference used at full power, and it is the template: a global, hidden regularity (a period) that no local sampling can see, revealed because amplitudes, unlike probabilities, can subtract. The same primitive breaks elliptic-curve cryptography, the basis of most modern key exchange.

Grover's algorithm (1996) tackles unstructured search: find the one marked item among $N$ possibilities when nothing about the problem guides you. Classically you must check about $N/2$ items on average. Grover finds it in about $\sqrt{N}$ steps.

The mechanism is amplitude amplification. Start in an equal superposition over all $N$ items. Each Grover iteration applies two reflections: one flips the sign of the marked item's amplitude, the other reflects every amplitude about the average. The combined effect rotates the state a small, fixed angle toward the answer, and after $\tfrac{\pi}{4}\sqrt{N}$ iterations the marked item holds nearly all the probability.

Two properties keep expectations honest. First, $\sqrt{N}$ is provably optimal for unstructured search: no quantum algorithm can do better, so "exponential search speedup" claims are wrong by theorem. Second, a quadratic speedup is fragile in practice: it must outrun the error-correction slowdown and the fact that classical search parallelizes trivially across a warehouse of machines while Grover does not. Current resource estimates generally place practical Grover advantage far beyond near-term machines, which is also why doubling a symmetric key length (AES-128 to AES-256) is considered a sufficient response.

Concreteness beats intuition here. Searching a space of a million items ($N = 2^{20}$):

Classical expected checks : N/2           = 524,288
Grover iterations         : (pi/4)*sqrt(N) = ~804
Nominal speedup           : ~650x

Now price in the machinery (illustrative rates):
  classical check         : 1 ns    (one memory probe, parallelizable)
  logical Grover step     : 100 us  (error-corrected, sequential)

Classical wall-clock      : 524,288 * 1 ns    = ~0.5 ms
Quantum wall-clock        : 804 * 100 us      = ~80 ms

The quantum machine loses by ~160x despite executing 650x fewer steps, because each step costs 100,000x more. Push $N$ high enough and Grover eventually wins the asymptotic race, but "eventually" here means search spaces so large that other constraints dominate.

The lesson generalizes: quadratic speedups need enormous problem sizes to pay for slow logical gates; exponential speedups (Shor, simulation) amortize the overhead almost immediately. This single calculation explains most sober skepticism about near-term quantum advantage claims.

The third family is the oldest idea in the field, Feynman's original 1982 motivation: use a quantum system to simulate quantum systems. Molecules, materials, and nuclear matter are governed by the Schrödinger equation, and representing their state classically costs memory exponential in particle count. A quantum computer stores that state natively, qubit-for-orbital, and Hamiltonian simulation algorithms evolve it in polynomial time.

Why this is the least speculative application:

• The exponential gap is about representation, not a clever trick that a better classical algorithm might close. (Classical heuristics like density functional theory are powerful but systematically fail on strongly correlated systems: high-temperature superconductors, some catalytic centers, transition-metal chemistry.)
• The target problems are commercially real: catalyst design (nitrogen fixation's FeMo cofactor is the canonical benchmark), battery electrolytes, drug binding energies.

The sober caveats: resource estimates for chemically accurate simulations of interesting molecules still run to millions of physical qubits and days of runtime, and classical methods keep improving, so the crossover point keeps moving. But among all claimed applications, this one has the clearest structural argument for why quantum should win.

The most heavily marketed applications carry the weakest guarantees:

• Optimization (QAOA, annealing). Variational algorithms encode a cost function into a circuit and tune parameters hoping to land in low-cost states. On today's noisy machines they run, but no proven speedup over the best classical heuristics exists for practically relevant problems, and classical solvers are a fearsomely optimized moving target. Every claimed advantage so far has been matched or beaten classically after scrutiny.
• Machine learning. Early "exponential speedup" claims for quantum linear algebra (HHL-style algorithms) often assumed data could be loaded into superposition cheaply; for classical datasets that loading step can erase the advantage entirely. Several celebrated quantum ML speedups were later dequantized: classical algorithms were found with comparable scaling. Genuine advantage likely requires quantum data, states arriving from sensors or simulations, rather than spreadsheets.

None of this makes the research worthless; it makes the burden of proof specific. The durable rule: a quantum speedup must name the structure interference exploits, and survive comparison with the best classical method, not the most convenient one.

One pattern jumps out: the algorithms with proven speedups were designed around a mathematically explicit structure (a period, a reflection geometry, the Schrödinger equation itself). The families without proofs hope structure exists in messy real-world instances. That distinction, guaranteed structure versus hoped-for structure, is the single most reliable filter for evaluating any new quantum application headline.

Shor's algorithm has one consequence that does not wait for hardware: data encrypted today can be recorded today and decrypted later, once a large machine exists. This harvest-now, decrypt-later logic means long-lived secrets (state archives, medical records, infrastructure keys) are already exposed to a future adversary, whatever the timeline.

The response is post-quantum cryptography (PQC): new public-key schemes built on math problems with no known quantum speedup, chiefly lattice problems (finding short vectors in high-dimensional lattices). After an eight-year open competition, NIST finalized the first standards in 2024: ML-KEM (Kyber) for key exchange, ML-DSA (Dilithium) and SLH-DSA for signatures. Browsers, operating systems, and messaging protocols began deploying hybrid classical-plus-PQC key exchange, so that breaking the connection requires breaking both.

Note the elegant asymmetry: PQC runs on classical hardware; no quantum computer is needed to defend against one. And symmetric primitives (AES, SHA-2) survive with at most doubled key sizes, since Grover's quadratic dent is the worst known attack. The quantum threat to cryptography is real, specific, and, unusually for this field, already being handled.

Compress this path into a working mental model:

1. The mechanism is interference (lesson 1): amplitudes cancel; algorithms are choreography.
2. Hardware is a trade-space (lesson 2): speed vs fidelity vs connectivity vs scale; judge machines by operations-per-coherence-window and error per useful circuit.
3. Logical qubits are the unit of account (lesson 3): below-threshold error correction converts qubit quantity into qubit quality at ~1,000:1 overhead; that conversion now works experimentally.
4. Applications inherit their credibility from structure (this lesson): factoring and simulation have it by theorem; optimization and ML must earn it instance by instance.

With that model, any announcement becomes legible. "We built N qubits" → ask about error rates and logical qubits. "Quantum advantage on task X" → ask whether X has proven structure and whether the best classical method was the comparison. "Q-day is near" → note that PQC deployment, not panic, is the operative response.

A field that once asked "is this possible?" now asks "what does it cost, and when does it pay?" Those are engineering and economics questions, and they are exactly the kind this path has equipped you to reason about.