## 2 Idea of Better Quantum Optimization  
The QAOA is a gate-based hybrid classical quantum algorithm inspired by the adiabatic theorem. The adiabatic theorem states that a quantum system initially in an eigenstate will remain in that eigenstate if the Hamiltonian governing the system changes sufficiently slowly [8]. The core idea of QAOA is to approximate this adiabatic process using a sequence of quantum gates, enabling the transition from an easy-to-prepare initial state to a state that approximates the solution to a given optimization problem. To implement this, QAOA uses a combination of two Hamiltonians: \(H_{C}\), the problem Hamiltonian, and \(H_{M}\), the mixing Hamiltonian. The evolution is discretized using the Lie-Trotter product formula [9], resulting in a sequence of alternating unitary operations. The final state of the algorithm after \(p\) steps is given by:  
\[|\psi_{p}(\overrightarrow{\gamma},\overrightarrow{\beta})\rangle=e^{-i\beta_ {p}H_{M}}e^{-i\gamma_{p}H_{C}}\ldots e^{-i\beta_{1}H_{M}}e^{-i\gamma_{1}H_{C }}|+\rangle^{\otimes R}. \tag{1}\]  
We can clearly see that the problem Hamiltonian serves a dual role in QAOA. Firstly, it acts as a quantum observable, measuring the energy of the system and providing feedback to adjust the variational parameters \(\overrightarrow{\gamma}\) and \(\overrightarrow{\beta}\). Secondly, it defines the structure of the quantum circuit, determining the gates and operations required for the algorithm. Because the Hamiltonian directly influences both the optimization process and the quantum circuit's complexity, it is beneficial to simplify and reduce its complexity wherever possible. A simpler Hamiltonian can lead to shorter quantum circuits with fewer entanglement gates, which, in turn, might increase the chances of achieving good results and solving larger problem instances. The structure of the Hamiltonian is also influenced by the chosen variable encoding of the problem. Often, a binary encoding is employed, where a qubit in the state \(|0\rangle\) indicates that a particular option is not selected, and \(|1\rangle\) indicates that it is selected. This encoding is straightforward for problems with binary variables. For problems with more than two choices, one-hot encoding is typically used. In one-hot encoding, a string of length \(m\) is constructed, where \(m\) corresponds to the number of possible choices. Each string is designed to have a Hamming weight of 1, meaning that only one qubit in the string is in the state \(|1\rangle\), while all others are in the state \(|0\rangle\). This ensures that only one option is chosen out of the \(m\) possible choices, providing a clear and unambiguous representation of the selection. There are two main approaches for encoding the one-hot constraint. The first approach uses the QUBO formulation:  
\[H_{\text{QUBO-onehot}}(x)=\left(\sum_{j=1}^{m}H_{x}(x_{j})-1\right)^{2}, \tag{2}\]  
where \(x_{j}\) is further replaced using the Pauli-\(Z\) term:  
\[H_{x}(x_{j})=\frac{1}{2}(I-Z_{j}), \tag{3}\]  
and the Pauli matrices are defined as follows:  
\[I= \begin{pmatrix}1&0\\ 0&1\end{pmatrix} ,\quad Z= \begin{pmatrix}1&0\\ 0&-1\end{pmatrix} .\]  
The encoding from Equation (2) has the advantage of using at most \(\frac{n(n-1)}{2}\) entanglements. However, if we need to sum many such partial Hamiltonians as constraints, we cannot derive any meaningful interpretation from the energy value, as this encoding increases quadratically with the Hamming distance from the one-hot encoding. If we want better interpretability, we can use entanglements with higher degrees, which are unavailable in, e.g., D-Wave quantum annealers, with the following formula:  
\[H_{\text{full-onehot}}=I-\sum_{j=1}^{m}\left(H_{x}(x_{j})\prod_{ \begin{subarray} {c}j=1\\ f\
eq j\end{subarray} }^{m}H_{\text{not}}(x_{j^{\prime}})\right), \tag{4}\]  
where  
\[H_{\text{not}}(x_{j^{\prime}})=\frac{1}{2}(I+Z_{j^{\prime}}). \tag{5}\]  
Equation (4) evaluates to 1 if and only if the one-hot value is encoded correctly, and it is 0 otherwise.