Grover's algorithm is the second most well-known algorithm (after Shor's) that was discovered in the 1990s and provides quantum advantage for a useful problem.

What the algorithm does, is, that it permits searching an unstructured data set for a particular value. Phrased in different words, it finds with high probability the unique input to a black box function that produces a particular output value. Classically, one has to search the data set for each item one by one until the sought-after data point is found. This means O(n) runtime, where n is the size of the data set. On a quantum computer, the result can be found with high probability in O(sqrt(n)) steps.

What is meant by an unstructured data set is that no assumptions are made regarding the properties of the data points, which means it can be applied to any search problem.

Grover's algorithm provides only a quadratic speedup. This is much less than the exponential speedup provided by a few select other algorithms, but still may be useful for certain practical applications. It is also important because can serve as a general subroutine to obtain quadratic run time improvements for some other algorithms.

The way it works can be understood by the so-called amplitude amplification trick. In our example, we implement Grover search on 7 qubits which means the data set has 2^7 entries. First, we prepare the input state by applying a series of Hadamard gates on the 7 input qubits and applying the X gate on the sixth ancilla qubit. Then we apply the Boolean Oracle function followed by the Grover Diffusion Operator on the 7 input qubits. The Oracle outputs 1 for the input state 1011111 (or 1111101 depending on your preferred qubit and bit ordering). The Grover Diffusion operator inverts the number stored in the first 7 qubits around the mean value. Together these two operators have the effect to perform the amplitude amplification trick where the amplitude of the sought-after result is increased while the amplitude of all other results is decreased. The combination of Oracle and Diffusion Operator needs to be applied 8 times. After this, the value of the input register can be measured and the sought-after value is determined with high (though not 100%) probability. Further applying the combination of Oracle and the Diffusion Operator, beyond after the optimum number of times, will decrease the probability of measuring the correct result.