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.

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.

11.1 Finding desired outcomes with Grover adaptive search

11.2 Finding optimal outcomes with the Grover optimizer

11.3 Solving the knapsack problem with a Grover optimizer

11.3.1 Preparing the state

11.3.2 Encoding constraints

11.3.3 Defining the parameters of the Grover optimizer

Summary