6.1 Grover’s algorithm

In this section, we will cover the most important properties of Grover’s algorithm. We will not cover all the theoretical details behind the procedure — for that, we recommend the book by Nielsen and Chuang [69] and, especially, the lecture notes by John Watrous [95] — but we need to at least get familiar with how the method operates, what oracles are and how they are used in the algorithm, and what kind of circuits are needed to implement it.

Let’s start with the basics. Grover’s algorithm is used for searching elements that satisfy certain conditions. More formally, the algorithm assumes that we have a collection of elements indexed by strings of bits, and a Boolean function that takes those binary strings and returns ”true” (or ) if the element indexed by the string satisfies the condition and ”false” (or ) otherwise. For instance, imagine that we are searching among 8 different elements...