## 2 Background
 \tag{3}\]  
The maximum of the cost function \(C_{max}\) is:  
\[C_{max}=\max_{z}C(z) \tag{4}\]  
The goal is to find a string \(z\) that achieves the highest approximate ratio of the calculated cost divided by the maximum cost, which is presented as:  
\[Approximate\ Ratio=\frac{C(z)}{C_{max}} \tag{5}\]  
The QAOA would like this value to be large, since this is a maximization problem. To encode the above as a quantum algorithm, we will need to define unitary operators. The first one depends on an angle \(\gamma\) and it is:  
\[U(C,\gamma)=e^{-i\gamma c}=\prod_{\alpha=1}^{m}e^{-i\gamma C_{\alpha}} \tag{6}\]  
The above cost function, also known as the cost Hamiltonian \(H_{c}\), is unitary and depends on the angle \(\gamma\in[0,\ 2\pi)\). Further, this unitary function can be written as the product of m unitary functions because each \(C_{\alpha}\) commutes. There is another operator, \(B\), which is the sum of \(\sigma^{x}\) operators and is defined as:  
\[B=\sum_{j=1}^{n}\sigma_{j}^{x} \tag{7}\]  
Another unitary operator, also known as the mixing Hamiltonian \(H_{B}\), depends on the angle \(\beta\in[0,\ \pi)\) and can be written as the product of \(n\) individual rotations of qubits by an angle \(\beta\) and is given as:  
\[U(B,\ \beta)=e^{-i\beta B}=\prod_{j=1}^{n}e^{-i\beta\sigma_{j}^{x}} \tag{8}\]Finally, the initial state \(\ket{s}\), the uniform superpositions of all the bitstrings \(z\), is expressed as:  
\[\ket{s}=\frac{1}{\sqrt{2n}}\sum_{z}\ket{z} \tag{9}\]  
For any integer \(p\geq 1\) and a set of \(2p\) angles \(\gamma_{1}\cdots\gamma_{p}\equiv\gamma\) and \(\beta_{1}\cdots\beta_{p}\equiv\beta\), the QAOA quantum circuit produces the following angle-dependent quantum state:  
\[\ket{\gamma,\beta}=U\big{(}B,\beta_{p}\big{)}U\big{(}C,\gamma_{p}\big{)}\cdots U (B,\beta_{1})U(C,\gamma_{1})\ket{s} \tag{10}\]  
The corresponding state is defined as:  
\[\ket{\overrightarrow{\gamma},\overrightarrow{\beta}}=\exp\big{(}-i\beta_{p} B\big{)}\exp\big{(}-i\gamma_{p}C\big{)}\cdots\exp(-i\beta_{1}B)\exp(-i\gamma_{1}C \big{)}\bigg{|}s\big{\rangle} \tag{11}\]  
The goal is to find the \(2p\) angles \(\gamma\) and \(\beta\) so that  
\[\bigg{\langle}\overrightarrow{\gamma},\overrightarrow{\beta}\bigg{|}C \bigg{|}\overrightarrow{\gamma},\overrightarrow{\beta}\bigg{\rangle} \tag{12}\]  
is maximized. It is not obvious how to choose good angles in advance, but there are several ways to find the optimal angles with classical optimizers using optimized iterations. Considering the above definitions, we started our study with the initial parameters, constructed the corresponding states, measured those states, and updated the angles. With layering and multiple iterations, the circuit was optimized, and the measurements of the output state provided an approximate solution. The steps of a high-level QAOA can be summarized as:  
Step 1: start with an initial state \(\ket{\psi}=\ket{s}\);  
Step 2: using a classical algorithm, initialize the \(2p\) parameters \(\gamma\) and \(\beta\);  
Step 3: construct \(\ket{\gamma,\beta}\) using the angles from step 2 and update the state \(\ket{\psi}_{new}\);  
Step 4: measure the state from step 3 and obtain a value \(\ket{z}\);  
Step 5: using a classical algorithm, calculate \(C(z)\);  
Step 6: repeat steps 1 to 4 several times, each time keep track and store the values of \(\ket{\gamma,\beta}\) and \(\ket{z}\);  
Step 7: select a new set of \(2p\) parameters \(\beta\) and \(\gamma\), and repeat steps 3 to 6. Choose the largest value for this distribution. Continue until the objective is met. Furthermore, a \(p\)-layer QAOA can be constructed by repeating the non-H gates (not Hadamard gates) for \(p\) times as shown in Figure 1. Each of the layers consists of cost Hamiltonian followed by mixing Hamiltonian, with the measurement being performed after the final \(p\)-layer resulting in the final quantum state.