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...

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...

6.2 Quantum oracles for combinatorial optimization

As we have seen, the Dürr-Høyer algorithm can be used to find the minimum of a function with high probability and with a quadratic speedup over brute force search. However, in order to use it, we need a quantum oracle that, given binary strings and , checks whether .

In our case, we are interested in functions that can appear in QUBO and HOBO problems. This means that will be a polynomial with real coefficients and binary variables, and we could implement the quantum oracle with a straightforward approach: design a classical circuit for it using AND, OR, and NOT gates, and then simulate the classical gates with the Toffoli quantum gate, as we showed in Section 1.5.2.

However, in 2021, Gilliam, Woerner, and Gonciulea, introduced an improved way of implementing quantum oracles for QUBO and HOBO problems in a paper titled Grover adaptive search for constrained polynomial binary optimization [45].

In this section, we will...

6.3 Using GAS with Qiskit

If you want to practice what you have learned in this chapter about Grover’s search, the Dürr-Høyer algorithm, and the construction of oracles, you can try to implement your own version of GAS in Qiskit from scratch. It is not a difficult project and it can be very satisfactory. However, there is no need for that. In the Qiskit Optimization module, you can find a ready-to-use implementation of Grover Adaptive Search (we will be using version 0.4.0 of the package). Let’s see how to use it.

One additional advantage of working with Qiskit’s GAS implementation is that it accepts the optimization problem format that we used with QAOA in Section 5.2.2. The simplest way of using it is by defining a QUBO problem like the one that we can create with the following piece of code:

from qiskit_optimization.problems import QuadraticProgram 
 
qp = QuadraticProgram() 
 
qp.binary_var(’x’) 
 
qp.binary_var(’y’) 
...

Summary

In this chapter, we have learned about Grover’s search algorithm and how it can be adapted to find minima of functions with the Dürr-Høyer algorithm. We have also learned about quantum oracles and their role in these two methods.

After that, we learned how to perform arithmetic in phase encoding and how to retrieve the results by using the mighty Quantum Fourier Transform. We also studied how to use all these techniques to implement oracles that can be used in Grover’s Adaptive Search to solve combinatorial optimization problems.

Finally, we also learned how to use GAS with Qiskit to obtain solutions of both QUBO problems and constrained quadratic programs.

Now, get ready for the next chapter: we will be studying the Variational Quantum Eigensolver and some of its most important applications!