11 Search-based quantum optimization
This chapter covers
- Searching for desired outcomes with Grover adaptive search
- Finding the maxima or minima of a polynomial function using a Grover optimizer
- A solution for the knapsack problem
Grover’s algorithm can offer a quadratic speed increase (in the number of queries) over classical approaches for certain optimization problems. We have discussed using Grover operators in several contexts, including search, quantum counting, and amplitude estimation.
Note Remember, to implement Grover’s algorithm for a given operator A that prepares the quantum state to be searched and a quantum oracle O, we build the Grover operator G. Then we can use the operator GjA to increase the probability of the outcomes tagged by the oracle, with a well-chosen integer j > 0.
In this chapter, we introduce a method called Grover adaptive search (GAS) that uses Grover’s algorithm to solve optimization problems where the number of good outcomes is not known. We will use GAS to build a Grover optimizer, a hybrid algorithm that dynamically adjusts the number of iterations and the parameters of the circuit that prepares the state to be searched to efficiently find optimal solutions. Then we will use the Grover optimizer method to find a solution to the knapsack problem. The concepts introduced in this chapter are outlined in figure 11.1.