11 Search-based quantum optimization

This chapter shows how Grover’s algorithm can be repurposed from unstructured search to search-based optimization. It introduces Grover Adaptive Search (GAS) to cope with unknown numbers of “good” solutions and then builds a Grover optimizer, a hybrid loop that interleaves quantum searches with classical updates to efficiently push toward global optima. With carefully chosen iteration schedules and a stopping rule, the approach aims for a quadratic reduction in oracle calls while remaining practical on near-term devices.

Grover Adaptive Search assumes a state-preparation circuit A, a problem oracle O that tags desirable outcomes, and the Grover operator G. Because the ideal iteration count depends on the (unknown) fraction of good states, GAS tries a sequence of iteration counts (e.g., simple [0, 1] schedules or more elaborate patterns), performs measurements, and checks for success, halting when a stopping condition is met. The chapter illustrates this with function encoding: map inputs to outputs via a polynomial of binary variables, represent signed integers in Two’s Complement, and use an oracle that tags non-negative outputs by inspecting the sign bit. Even a single Grover iteration can dramatically amplify the probability of measuring a desired outcome, while the surrounding orchestration and decision logic remain classical.

Building on GAS, the Grover optimizer repeatedly tightens the search by updating the encoded function so that the current best result becomes the new threshold: for maximization, shift the function so the latest best value becomes negative, then search again for non-negative outcomes. A worked example finds the maximum of a concave quadratic, demonstrating the hybrid loop of prepare–search–assess–update. The method then solves a small knapsack instance by encoding three registers—selection, value, and weight—adjusting constraints with transformations like w′ = capacity − w and raising the value threshold v′ = v − min_value, and using a multi-register oracle that tags feasibility and quality via sign bits. Practical guidance includes iteration schedules, stopping criteria, register sizing for signed arithmetic, and leveraging classical heuristics to seed the quantum search and accelerate convergence.

A dependency diagram of concepts covered in this chapter.

A flow diagram of Grover Adaptive Search.

The quantum state encoding the function \(f(k) = k^2 - 5\) with \(0 \le k < 4\).

The quantum state encoding the function \(f(k) = k^2 - 5\) with \(0 \le k < 4\) after applying one Grover iteration.

The quantum state encoding the function \(f(k) = k^2 - 5\) with \(0 \le k < 4\) after applying two Grover iterations.

A flow chart of the Grover optimizer.

Construct or update the circuit \(A\). These parameters are updated depending on the results of the previous search.

The grid state representation of the quantum state encoding the function \(f(k) = -(k-3)^2 + 3\).

Choose a schedule that determines the number of iterations \(r \ge 0\) to be performed at each step.

Apply the Grover operator \(G^r A\), where \(r\) is the number of iterations according to the chosen schedule.

Check if the result of this search is better than the result at the previous step (or the default value).

If progress was not made, check the stop condition.

The grid state representation of the quantum state encoding the function \(f(k) = -(k-3)^2 + 3\) and applying one Grover iteration.

Check if the result of this search is better than the result at the previous step (or the default value).

Construct or update the circuit \(A\). These parameters are updated depending on the results of the previous search.

The grid state representation of the quantum state encoding the function \(f(k) = -(k-3)^2 + 3\) shifted by -4.

Once the stopping condition is met, the optimal value is returned.

Three registers encoding an item selection, its total value, and its total weight for solving the knapsack problem.

A quantum state after encoding the values and weights of each possible selection.

The selection register outcome probabilities after looking for selections with a maximum weight of 4 and a minimum value of 3.

The selection register outcome probabilities after looking for selections with a maximum weight of 4 and a minimum value of 4.

• We can encode multiple (polynomial) functions of the same binary variables in different registers of a quantum circuit. The functions can represent a value or cost associated with the inputs.
• A Grover optimizer iteratively uses Grover’s algorithm to find optimal values or costs by using previous best results to narrow the size of the search space.
• The key to an efficient Grover optimizer is using an efficient underlying oracle. Searching for negative or non-negative integers can be done with oracles using the Two’s Complement interpretation.

FAQ