# Improving the Solving of Optimization Problems:
## 5 Quantum Circuit Model-Based Solvers
### Qaoa  
The Quantum Approximate Optimization Algorithm (QAOA) [55] is a hybrid quantum-classical algorithm introduced in [56], designed to solve optimization problems approximating the quantum AQC on gate-based quantum computers (discussed in Section 4.1). Starting from an Ising Hamiltonian, it has to be reformulated as a quantum Hamiltonian formulation by replacing the binary variables with Pauli \(Z\) matrices, since the eigenvalues of this matrix are \(+1\) and \(-1\). \[H_{1}=\sum_{i}h_{i}\sigma_{i}^{z}+\sum_{i,j}J_{ij}\sigma_{i}^{z}\otimes\sigma_ {j}^{z}. \tag{11}\]  
Quantum circuit model computers nature operate by applying discrete quantum gates to modify the qubit's state, while AQC depends on a continuous evolution of the Hamiltonian. This evolution can be discretized through the Trotterization technique, which approximates it in discrete steps. The AQC time-dependent Hamiltonian (Equation (7)) can be discretized for the execution of quantum gates by expressing it as a product of unitary operators performing a small evolution step. Since \(H(t)\) is diagonal in the quantum system computational space, i.e., a \(2^{n}\times 2^{n}\) Hilbert space, it can be made unitary by exponentiating \(H(t)\), which corresponds to taking the exponential of its elements. The discretized operator can be obtained by considering the evolution only in a small time instant \(\Delta t\):  
\[e^{i\Delta t(A(t_{c})H_{0}+B(t_{c})H_{1})}, \tag{12}\]where \(t_{C}\) is a fixed timestep within the range \([0,T]\), with \(T\) being the total duration of the process. In a small time interval \(\Delta t\), the Hamiltonian can be assumed to be constant. By discretizing the process into \(p\) steps, the Hamiltonian becomes  
\[\prod_{m=0}^{p}e^{i\Delta t\left(A(t_{m})H_{0}+B(t_{m})H_{1}\right)}\,, \tag{13}\]  
where \(t_{m}=m\Delta t/T\) and \(p=T/\Delta t\). According to the Lie-Trotter product formula, if \(\Delta t\) is very small, \(e^{A+B}\approx e^{A}e^{B}\) with \(A,B\) being two square complex matrices. Furthermore, by selecting \(A(t_{m})\) and \(B(t_{m})\) as small increments of time, the quantum circuit simulates the adiabatic evolution of the Hamiltonian. However, instead of \(A(t_{m})\) and \(B(t_{m})\), two angles, \(\gamma\) and \(\beta\), can be chosen at each iteration of the parametric circuit according to a classical optimization algorithm to obtain the best values for reaching the ground state of the Ising Hamiltonian. The quantum part of QAOA is performed by a variational quantum circuit--i.e., a circuit including parametric gates, whose value has to be optimized during algorithm execution--preparing the following state:  
\[|x\rangle=\prod_{m=p}^{0}e^{i\beta_{m}H_{0}}e^{i\gamma_{m}H_{1}}|\Psi_{0}\rangle =\prod_{m=p}^{0}U_{M}(\beta_{m})U_{c}(\gamma_{m})|\Psi_{0}\rangle\,. \tag{14}\]  
To keep the analogy with the quantum adiabatic algorithm and ensure the system evolves while keeping the quantum state as the ground state of the evolving Hamiltonian, \(\Psi_{0}\) must be the ground state of \(H_{0}\). A suitable choice for the mixed Hamiltonian is the tensor product of \(n\) Pauli X operators (\(\sigma_{j}^{x}\)) with a negative sign, with \(n\) being the number of qubits. Given a quantum state \(|\Psi\rangle\), the expectation value of the operator \(\sigma_{j}^{x}\) in this state is as follows:  
\[\langle\Psi|X_{j}|\Psi\rangle=2c_{0}c_{1}\leq 1,\quad\text{with}|\Psi\rangle=c_{0 }|0\rangle+c_{1}|1\rangle, \tag{15}\]  
which is equal to 1 only when \(c_{0}=c_{1}=1/\sqrt{2}\); thus, the expectation value is maximum when \(|\Psi\rangle=|+\rangle\). Therefore, \(H_{0}\) is specifically chosen because its ground state is \(|\Psi_{0}\rangle=\bigotimes_{j=0}^{n-1}|+\rangle\), which is straightforward to prepare, as it can be obtained by applying \(n\) Hadamard gates and is completely unentangled.