# Improvement of Quantum Approximate Optimization Algorithm for Max-Cut Problems
## 1 Introduction
This optimization challenge is already known as the Max-Cut problem, and it is one of the most studied combinatorial optimization problems because of its wide range of applications and because of its connections with other fields of discrete mathematics [15]. Different solutions have been proposed for the Max-Cut type of problems, as it belongs to the so-called NP-hard complexity class problems, where no known algorithms are able to solve NP-hard problems in polynomial time and thus exact methods rapidly become intractable. Such solutions include search-based algorithms [16], Machine Learning alternatives [17], as well as Recurrent Neural Networks and Reinforcement Learning [18; 19]. Quantum approaches were also proposed with a quantum approximate optimization algorithm (QAOA) by [20]. The QAOA belongs to the class of hybrid algorithms and requires, in addition to the execution of shallow quantum circuits, a classical optimization process to improve the quantum circuit itself. The QAOA is an algorithm that uses unitary transformations \(U(\beta_{i},\gamma_{i})\), depends on two parameters \(\beta_{i}\) and \(\gamma_{i}\), and is arranged in alternating blocks a number \(p\) of times (\(i\in\{1,\ldots,p\}\)) given by  
\[|\psi(\overrightarrow{\beta},\overrightarrow{\gamma})\rangle=\underbrace{U( \beta_{i})U(\gamma_{i})...U(\beta_{i})U(\gamma_{i})}_{p\text{ times}}|\psi_{0}\rangle \tag{1}\]  
where \(|\psi_{0}\rangle\) is a suitable state and parameters \(\overrightarrow{\beta},\overrightarrow{\gamma}\in\mathbb{R}^{p}\). The goal of the algorithm is to find the combination of parameters that allows a quantum state \(|\psi(\overrightarrow{\beta_{opt}},\overrightarrow{\gamma_{opt}})\rangle\) to yield the optimal solution [21]. This heuristic algorithm produces then a bit string \(x\in\{0,1\}^{n}\) that with high probability is expected to give a good approximation of the theoretical solution. The algorithm follows a classical optimization scheme: first prepares a parameterized quantum state \(|\psi(\overrightarrow{\beta},\overrightarrow{\gamma})\rangle\) (called the ansatz), then computes the parameters \((\overrightarrow{\beta_{opt}},\overrightarrow{\gamma_{opt}})\) such that the expectation value of the quantum state is given by  
\[F_{p}=\langle\psi(\overrightarrow{\beta},\overrightarrow{\gamma})|\,H_{p}\,| \psi(\overrightarrow{\beta},\overrightarrow{\gamma})\rangle \tag{2}\]  
is maximized with respect to the problem Hamiltonian \(H_{p}\), and finally performs a classical optimization until some convergence criterion is reached. An overview of this is shown schematically in Figure 1.  
The convergence criterion is in the Max-Cut cost function given by  
\[C(x)=\sum_{i,j=1}^{n}x_{i}(1-x_{j}), \tag{3}\]  
which can be mapped to a Hamiltonian that is diagonal in the computational basis by  
\[H=\sum_{x\in\{0,1\}^{n}}C(x)\ket{x}\bra{x}, \tag{4}\]  
in which \(x\in\{0,1\}^{n}\) labels the computational basis states \(\ket{x}\in\mathbb{C}^{2^{n}}\). The expansion of \(Z_{i}= \begin{pmatrix}1&0\\ 0&-1\end{pmatrix} \) Pauli-Z operators can be obtained from the canonical expansion of \(C(x)\) by substitution of every variable \(x_{i}\in\{0,1\}\) by the matrix \(\frac{1}{2}(1-Z_{i})\). As indicated in the abstract, this paper aims to show that the already suggested approximate solution can be improved. The proposal for an alternative quantum algorithm configuration improves the existing solutions up to thirty nodes. The optimization algorithm proposed in [PERSON] et al. [20] promotes a specific sequence of unitary operators, which means an effective expression for the Hamiltonian. Finally, such a sequence of transformations will perform differently when the size of the circuit evolves. Our approach can be understood in the end as a proposal for a different sequence of unitary operators, providing a different configuration for the Hamiltonian. Then, what it is claimed is that our algorithm (our effective expression for the Hamiltonian) performs much better than the existing one.