Grover's algorithm is the other famous quantum algorithm, and probably the most misunderstood.
The problem: you have an unstructured space of N items and a function f(x) that answers "is this the one?". Classically, you try items one at a time, and on average you check N/2, worst case N. Grover finds the item with about (π/4) √N evaluations of f.
Three honest caveats:
- It is quadratic, not exponential.
Nbecomes√N. For a brute-force search over2^nkeys, that is2^(n/2)steps: a real gain, but you can respond by doubling the key length. - You can overshoot. The algorithm rotates the state towards the answer in small steps. Run too many iterations and you rotate past it, and the success probability goes down again. You need to know
Nand the number of solutions to stop at the right time. - The "oracle" is not free. Somebody has to implement
fas a quantum circuit, and its cost is part of the cost of each iteration. If checking a candidate is expensive, the speed-up is applied to an expensive thing.
The structure is lovely: repeat "flip the sign of the right answer's amplitude", then "reflect all amplitudes about their average". Each round nudges the amplitude of the right answer up a bit. Interference again.
And, a result worth knowing: for unstructured search, √N is optimal. No quantum algorithm can do better without structure to exploit.