Summary

Grover’s algorithm speeds up the search of an unordered list. We represent a list of size N with n qubits, where N = 2n. Eventually, when we measure the qubits, we see a combination of n bits. Each possible combination stands for an element in the list. Each step of Grover’s algorithm increases the probability that the measurement outcome represents the target of our search.

The optimal number of steps depends on the number of elements in our unordered list. Each step of Grover’s algorithm makes approximately the same number increase in the target combination’s amplitude. Since an amplitude is the square root of a probability, the optimal number of steps grows with . That’s better than a classical search, where the optimal number of steps grows with N.

Grover’s search can be useful when it’s easy to verify that a particular element is the search target but difficult to find the search target among all the choices. Problems...