Go further · Chapter 7 · 7b · A step deeper
What else can quantum computers do besides break codes?
The short answer (tap to open)
Two other big ideas. Grover's algorithm finds a marked item in an unsorted list in about the square root of the usual number of tries: a thousand instead of a million. Quantum simulation uses qubits to model molecules and materials, which are quantum themselves, and is the most promising long-term use, from fertilisers to batteries.
How does Grover's search work?
Imagine a list of a million unlabelled boxes, one holding a prize. An ordinary search opens boxes one by one: on average half a million tries.
Grover's algorithm, from 1996, starts with every box at an equal, tiny amplitude. Then it repeats two steps:
- Mark: flip the sign of the prize box's amplitude (it now points down instead of up).
- Reflect: flip every amplitude around the average. The marked one, being below average, bounces up above everyone else.
Each round grows the prize's amplitude and shrinks the rest. After about 800 rounds for a million boxes, measuring almost certainly gives the prize.
Round 0 · odds of the prize: 6%
The prize's odds after each round
| Rounds | Odds of the prize |
|---|---|
| 0 | 6% |
| 1 | 47% |
| 2 | 91% |
| 3 | 96% |
| 4 | 58% |
Overshoot: Grover's search has a sweet spot.
Is that a big deal?
It's a square-root speed-up: a million tries become about a thousand. Useful, but modest, and ordinary computers often get similar gains by being clever about the problem. In practice, the overheads of error correction can eat the advantage for many real searches. Grover's real importance is as a building block inside other algorithms, and for encryption: it halves the effective strength of keys like AES, which is why the fix is simply to use longer keys (chapter 13).
Why simulate molecules?
Molecules hold electrons that obey quantum rules and entangle with one another. Describing them exactly on an ordinary computer runs into chapter 7's doubling problem: each extra electron orbital roughly doubles the work. So chemists use clever approximations, which work well for many molecules and fail for some of the most important ones.
A quantum computer uses qubits to stand in for the electrons directly. Richard Feynman suggested exactly this in 1981 (page 7c).
Which problems are worth it?
The usual examples:
- Fertiliser. Making ammonia by the Haber-Bosch process uses a few per cent of the world's natural gas. A bacterial enzyme does it at room temperature, using a metal cluster called FeMoco that ordinary computers can't model accurately.
- Batteries and materials: better electrolytes, magnets and superconductors.
- Medicines: how drug molecules bind, though much of drug discovery doesn't need quantum accuracy.
Studies estimate that modelling FeMoco well needs a few thousand high-quality logical qubits: far beyond today's machines, but one of the clearest targets on every roadmap (chapter 14).
Check
Two quick ones
Collect
Your aha card
Two more tools: a square-root search and a quantum model of nature.
Simulation is the strongest long-term case.