If you take one thing from this track, take this lesson. Being able to say clearly what a technology cannot do is what separates someone worth listening to from someone repeating a press release.
| Classical | Quantum | |
|---|---|---|
| Unstructured search | O(N) queries | O(√N) — Grover, and this is provably optimal |
| Factoring an n-bit number | sub-exponential (GNFS) | polynomial in n — Shor |
| Simulating quantum systems | exponential in system size | polynomial — the original motivation |
| NP-complete problems | exponential (believed) | still exponential (believed) — no free lunch |
The big one: hard planning problems stay hard
Route planning, timetabling, packing a lorry, the travelling salesman. Quantum computers are not expected to crack these.
Grover helps a bit — it square-roots the search. But square-rooting an impossibly big number leaves you with a still-impossibly-big number. A genuinely hard case stays hard.
Big wins need a hidden pattern
The enormous speed-ups only appear when the problem has some hidden regularity to grab onto. Codebreaking has a repeat in it. Chemistry works because the machine and the problem are made of the same stuff.
Most real-world problems have no such structure, and after thirty years of looking, nobody has found a way in.
Three costs that get left out of the headline
Getting data in. Loading a big dataset into a quantum computer can cost more than the calculation. Any claim that assumes the data is already in there has moved the problem, not solved it.
Getting answers out. One look, one answer. An algorithm that produces a beautiful quantum state you cannot read is not finished.
Fixing errors. Around a thousand ordinary qubits per reliable one, plus a slowdown on every step. A modest speed-up can disappear into this entirely.
Four questions for any claim
Faster than what?
The best ordinary method, or an easy target?
Measured how?
Questions asked, or actual time on an actual machine?
On what hardware?
Does it assume machines that do not exist yet?
Add a fourth: who wanted this problem solved? A surprising number of demonstrations are on problems invented to suit the method.
Being able to say what a technology cannot do is what earns you the right to be believed about what it can.
Worth remembering
- Hard planning problems are not expected to become easy. Grover only square-roots the search.
- Huge speed-ups need hidden structure, which most real problems lack.
- Loading data, reading answers and fixing errors are routinely left out of claims.
- Ask: faster than what, measured how, on what hardware, and who wanted it?