## 2 Background  
Problems with discrete variables are classified as combinatorial optimization problems. Combinatorial optimization is the process of finding an optimal or close-to-optimal solution among a finite set of possibilities. Formally, an instance of an optimization problem \(I\) is a pair \((F,c)\), where \(F\) is the domain of feasible points, and \(c\) is the cost function [10], and the goal is to find a globally optimal solution \(f\in F\) to the given instance \(I\) so that  
\[c(f)\leq c(y)\;\;\text{for all}\;y\in F \tag{1}\]  
In other words, we look for an object (integer, set, permutation, or graph) from a finite or, possibly, countably infinite set. In classical computing, some of these problems can be solved exactly using branch and bound techniques. But in many cases, such as the TSP (an NP-hard problem), exact algorithms are infeasible, and therefore, randomized-search algorithms, such as the genetic algorithm, particle swarm optimization, simulated annealing, and alike, are used [4]. Due to the constraints and the complexities of such problems, at the very core, two important factors are to be considered--the _time_ to find an optimal solution, and the _quality_ of that solution. The optimal solution is obtained from a finite set of solutions. The TSP is a classic combinatorial optimization problem that can be described as follows. Given the \((x,y)\) positions of \(n\) different cities, we need to find the shortest possible path that visits each city exactly once. The TSP belongs to a class of NP-complete combinatorial problems and is classified as an NP-hard problem because for \(n\) cities, \((n-1)!\) possible combinations are needed to search for the solution, and the number of combinations grows fast as \(n\) increases. This cycle of visiting each city once, where each city represents a unique vertex in a graph, and returning to the starting city is known as a _Hamiltonian_ cycle. Each city is connected to other cities with a specific cost associated to each connection. Quantum data are remarkably interesting as information can be in the superposition of states. When we increase the number of qubits, the Hilbert space (the state space), grows exponentially with the number of qubits, as \((\ket{0}+\ket{1})^{n}\). If \(n=50\), the operation can behandled by today's supercomputers; however when \(n=300\), then we will have more states than atoms in the universe. Thus far, the number of reliable quantum operations have been limited by noise and decoherence, and therefore, hybrid quantum-classical algorithms were introduced with the aim to combine the best of both worlds. The QAOA [7] and the variational quantum eigensolver [11] are examples of such hybrid quantum-classical algorithms aimed to address some of the classical combinatorial optimization problems. These algorithms use a quantum circuit depending on a set of parameters which are determined by a classical optimizer. The QAOA is a promising algorithm to tackle these problems in the Noisy Intermediate-Scale Quantum (NISQ) technology. The QAOA applies alternatively a cost function-based Hamiltonian and a mixing Hamiltonian. The goal is to maximize the cost function. It is a polynomial-time algorithm for finding a nearly optimal solution to an optimization problem. We are interested in combinatorial optimization problems specified by \(n\) bit binary strings and \(m\) clauses [7]. The objective function \(C(z)\), which is the sum of the individual cost functions from \(m\) clauses, is:  
\[C(z)=\sum_{\alpha=1}^{m}C_{\alpha}(z) \tag{2}\]  
where \(z=z_{1}\cdots z_{n}\) is the bit string, and \(C_{\alpha}(z)\) depends on only a few of the \(n\) bits, and its satisfiability is described as:  
\[C_{\alpha}(z)= \begin{cases}1&\to satisfies\cr 0&\to does not\ satisfy\end{cases}