9.7 Searching

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 the ket , which I knew about, can be picked out of all the kets. So I found what I knew was there, and I even knew where it was beforehand. Here we put everything together to describe the famous quantum search algorithm discovered by Lov Kumar Grover, a computer scientist.

9.7.1 Grover’s search algorithm

Instead of using the magic gate matrix , which flips the sign of the amplitude of the given ket, we instead employ U_f, which is related to the oracle f.

In essence, I have an oracle which I can call but I cannot see. I create U_f and then by repeating U_f U_ϕ enough times, I can find the special element for which f returns 1. How many times is enough?

In subsection...