Grover adaptive search (GAS) is a hybrid quantum-classical technique for optimization when the number of good outcomes is unknown. It repeatedly prepares a state with circuit A, applies a scheduled number of Grover-operator iterations, measures, and classically checks the result. section 11.0 section 11.1
A GAS search loop follows this pattern:
- Choose an iteration count r from a schedule, including zero when measuring directly without applying the Grover operator. section 11.1
- Prepare the initial state with A, apply r iterations of G, measure the result, and test whether it is good. section 11.1
- Stop after a successful or sufficiently unsuccessful search, using conditions such as consecutive failures to find a good outcome. section 11.1 section 11.4
Schedules may select iteration counts randomly from exponentially growing ranges or follow fixed patterns. A simple implementation uses the two-count schedule [0, 1] with multiple-shot computations, avoiding the expense of quantum counting. section 11.1
Searching a polynomial encoding
For f(k) = k² − 5 with 0 ≤ k < 4, the encoded values are −5, −4, −1, and 4. An oracle can mark a selected value; applying one or two Grover iterations changes the measured outcome probabilities. The same pattern supports a Grover optimizer for maxima or minima by updating the encoded function after successful measurements to restrict later searches to better solutions. section 11.1 section 11.4
Figure 11.2 A flow diagram of Grover adaptive search
Use the flow diagram to trace scheduling, quantum execution, measurement, classical evaluation, and repetition. section 11.1
