9.7 Searching with Grover
We just saw how if we have one standard basis ket in mind, we flip the probability amplitude and then amplify the amplitude for that ket. When we repeat the process enough times, we are likely to measure the right ket with high probability.
In the last section, I showed that we could pick out the known ket |010⟩ from among all the kets. So I found what I knew was there, and even knew where it was beforehand. We can use these techniques more generally. In this section, we put everything together to describe the famous quantum search algorithm discovered by Lov Kumar Grover, a computer scientist. The algorithm is based on amplitude amplification. Grover, Lov Kumar
9.7.1 Grover’s search algorithm
Instead of using the magic gate matrix U|010⟩, which flips the sign of the amplitude of the given ket, we instead employ Uf, which is related to the oracle f. Grover’s search algorithm algorithm$Grover...
