Finding a needle in fewer tries

Suppose one name in a phone book of a million has a star next to it and you can only check one name at a time. On average you check half a million. There is no shortcut for an ordinary computer.

Grover's method starts by putting all million names in superposition, each with the same small amplitude. Then it does two things, over and over. First, it flips the sign of the starred name's amplitude, crest to trough. Second, it reflects every amplitude about the average. The starred one, being the odd one out, gets pushed up; the rest get pushed down by a hair.

Each round the starred amplitude grows. After about a thousand rounds, the square root of a million, it is nearly all the wave, and a measurement reads it out. Go too many rounds and it starts shrinking again, so you have to count.

That is a square-root speed-up. A million to a thousand is good. A trillion to a million is better. It is not the exponential leap of Shor's method, but it applies to almost any search or optimisation you can phrase as 'check whether this guess is right', which is why it comes up so much.

It has also been proved you cannot do better than the square root for a plain unsorted search. The quantum computer is not magic here. It is a wave doing what a wave can do.