Amplitude Amplification

Applications

Assume we have an unsorted database with N elements, and an oracle function which can recognize the good entries we are searching for, and for simplicity.

If there are G such entries in the database in total, then we can find them by initializing the quantum computer into a uniform superposition

of all the database elements, and running the above algorithm. In this case the overlap of the initial state with the good subspace is equal to the square root of the frequency of the good entries in the database, . If, we can approximate the number of required iterations as

$n = \left\lfloor\frac{\pi}{4\theta}\right\rfloor \approx \left\lfloor\frac{\pi}{4 \sin(\theta)}\right\rfloor = \left\lfloor\frac{\pi}{4} \sqrt{\frac{N}{G}}\right\rfloor = O(\sqrt{N}).$

Measuring the state will now give one of the good entries with a high probability. Since each application of requires a single oracle query (assuming that the oracle is implemented as a quantum gate), we can find a good entry with just oracle queries, thus obtaining a quadratic speedup over the best possible classical algorithm.

If we set G to one, the above scenario essentially reduces to the original Grover search.

Read more about this topic: Amplitude Amplification

Amplitude Amplification - Applications