A quantum algorithm is not "the normal method, but on a quantum computer". It has a particular shape, and nearly every one that works has the same three steps.
The shape
1. Spread out. Put every qubit into an even mixture, so the machine now holds every possible input at once. This bit is easy and cheap, and it is not where the speed comes from.
2. Mark the answer. Do something that treats the right answer differently from all the others — usually by sticking a minus sign on it. Nothing you could see has changed yet.
3. Make the mark show up. Arrange for all those minus signs to cancel the wrong answers away, so the right one is what is left when you look.
Skip step three and you get a random input. That is the single most common misunderstanding about this whole field, and now you are past it.
How "faster" gets counted
Papers in this field almost never measure speed in seconds. They count questions asked — how many times you have to consult the problem.
There are two good reasons. It lets people prove things about what is impossible, and it does not depend on whose chip you are using.
| 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 |
Two very different kinds of "faster"
Enormously faster, like Shor. Dramatic — but it only turns up when the problem has a hidden repeating structure the machine can grab onto. There are not many such problems.
Somewhat faster, like Grover. It applies to almost any search, which is wonderful. But it takes a million steps down to a thousand, not down to ten — and the overhead of running a real quantum computer can eat most of that.
Worth remembering
- Spread out, mark the answer with a minus sign, then make the wrong answers cancel.
- The third step is the algorithm. Without it you get a random guess.
- Speed is counted in questions asked, so that limits can be proved.
- Huge speed-ups need special structure. Modest ones are general but easy to lose.