Chapter 6
GAS: Grover Adaptive Search
If you do not expect the unexpected, you will not find it, for it is not to be reached by search or trail.
— Heraclitus
In this chapter, we are going to introduce another quantum method for solving combinatorial optimization problems. In this case, we are going to take Grover’s algorithm — one of the most famous and celebrated quantum methods out there — as a starting point. Grover’s algorithm is used to find elements that satisfy specific conditions in unsorted data structures. But, as we will soon see, it can be easily adapted to function minimization tasks — exactly what we need for our optimization problems! The resulting method is sometimes called Grover Adaptive Search or GAS.
It is important to note that GAS is essentially different from the kind of quantum algorithms that we have been studying so far in this part of the book. This method is not designed specifically for NISQ devices and would need...
