# Improving the Solving of Optimization Problems:
## 5 Quantum Circuit Model-Based Solvers
### Gas  
The Grover Adaptive Search is a successive approximation hybrid quantum-classical algorithm designed to find the minimum of a cost function \(f(x)\), which represents a combinatorial optimization problem [67; 55; 68]. It is composed of the following steps:  
1. Initialize the iteration index \(i\) and the variable \(y_{i}\) to zero. 2. Adjust the cost function \(f(x)\) by vertically shifting it based on \(y_{i}\) (Figure 4). 3. Increment the iteration index \(i\). 4. Randomly sample a value \(y_{i}\) from the range of \(f(x)\) such that \(y_{i}<0\). 5. Consider \(y_{i}\) as the new optimal value, as a negative value of the adjusted cost function consistently indicates a lower value than the previous offset \(y_{i-1}\). 6. Repeat steps 2-5 until no further negative values are sampled. This process identifies the variable combination where \(f(x)=0\), solving the optimization problem. To fully leverage this approach, an efficient negative sampling method is crucial. The best option is a quantum routine that accelerates the process of finding solutions at each iteration. Grover Search (GS) [69] is a quantum algorithm offering a quadratic speedup over classical methods when searching for items in an unordered dataset. Initially, the objective function, shifted by \(y_{i}\), must be encoded into a quantum state as a uniform superposition of the domain-image obtained through a quantum dictionary [68], the quantum counterpart of a classical dictionary, which allows the description of key-value pair data structures. The image of \(f(\mathbf{x})\) is represented using the two's complement binary format for signed integers. Encoding an \(n\)-variable problem requires \(n\) qubits for the keys and \(m\)--sufficiently large to avoid overflow, based on the function bounds--for the values. Unfortunately, estimating the exact bounds has the same computational complexity as solving the problem via brute force, growing as \(2^{n}\). Thus, preprocessing is necessary to select an appropriate value for \(m\). Setting \(m\) too low compromises the mechanism's effectiveness, while setting it too high wastes limited resources. Several methods in the literature provide lower bounds for the minimum and, by addressing the negated problem, upper bounds for the maximum, typically requiring no more than a couple of additional qubits. The following equation describes the quantum dictionary operator \(U_{i}\):  
\[U_{i}|0\rangle_{n}|0\rangle_{m}=\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}|x \rangle_{n}|f(x)-y_{i}\rangle_{m}. \tag{22}\]  
At this point, the Grover phase oracle is applied to label the desired items of the dataset--in this case, the negative samples of the objective function--and the diffuser operator is employed to amplify the probability amplitude of the corresponding states. For implementing an effective GS, phase oracle and diffuser have to be repeated \(r\) times, where \(r\) is also called the number of GS rotations, and its optimal value depends on the dataset characteristics. It can be estimated through the following equation [70]:  
\[r\approx\frac{\pi}{4}\sqrt{\frac{2^{n}}{M}}-\frac{1}{2}, \tag{23}\]  
where \(M\) is the number of desired items, i.e., the negative samples, which is unknown a priori. This number of rotations ensures finding one of the \(M\) states with the maximum probability [7]; hence, either a too-high or too-low \(r\) may lead to an incorrect result. Its estimation in each GS execution is crucial, and some techniques were proposed in the literature for this purpose [68; 71; 72; 73]. The quantum circuit employed for GS execution in the GAS algorithm is reported in Figure 4.  
Once a negative value has been acquired, the function can be classically shifted by that amount and re-encoded in the quantum dictionary to sea  
Figure 4: GAS intuitive scheme. samples obtained are, with each iteration, closer to the function's minimum until the last negative is obtained, corresponding to the optimal solution. However, determining whether additional negative values need to be sampled is a crucial task.