# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 2 Related Work  
The QAOA was introduced by [1] where it was applied to the Max-Cut problem. The authors in [7] compared the QAOA to the classical AKMAXSAT solver extrapolate from small instances to large instances and estimate that a quantum speed-up can be obtained with (several) hundreds of qubits. A general overview of variational quantum algorithms, including challenges and how to overcome them, is provided in [8; 9]. Key challenges are that it is in general hard to find good parameters. It has been shown that the training landscapes are in general NP-hard [10]. Another obstacle is so-called barren plateaus, i.e., regions in the training landscape where the loss function is effectively constant [9]. This phenomenon can be caused by random initializations, noise, and over-expressablity of the ansatz [11; 12]. Since its inception, several extensions/variants of the QAOA have been proposed. _ADAPT-QAOA_[13] is an iterative, problem-tailored version of QAOA that can adapt to specific hardware constraints. A non-local version, referred to as _R-QAOA_[14], recursively removes variables from the Hamiltonian until the remaining instance is small enough to be solved classically. Numerical evidence shows that this procedure significantly outperforms standard QAOA for frustrated Ising models on random three-regular graphs for the Max-Cut problem. _WS-QAOA_[15] takes into account solutions of classical algorithms to a warm-starting QAOA. Numerical evidence shows an advantage at low depth, in the form of a systematic increase in the size of the obtained cut for fully connected graphs with random weights. There are two principal ways to take constraints into account when solving Equation (1) with the QAOA. The standard, simple approach is to penalize unsatisfied constraints in the objective function with the help of a so-called Lagrange multiplier \(\lambda\), leading to  
\[x^{*}=\operatorname*{arg\,min}_{x\in\{0,1\}^{\alpha}}\big{(}f(x)+\lambda g(x )\big{)}. \tag{9}\]  
This approach is popular, since it is straightforward to define a phase-separating Hamiltonian for \(f(x)+\lambda g(x)\). Some applications include the tail-assignment problem [16], the Max-k-cut problem [17], graph coloring problems, and the traveling sales person problem [18]. A downside of this approach is that infeasible solutions are also possible outcomes, especially for approximate solvers such as QAOA. This also makes the search space much bigger and the entire approach less efficient. In addition, the quality of the results turns out to be very sensitive to the chosen value of the hyperparameter \(\lambda\). On one hand, \(\lambda\) should be chosen large enough such that the lowest eigenstates of \(H_{P}\) correspond to feasible solutions. On the other hand, too large values of \(\lambda\) mean that the resulting optimization landscape in the \(\gamma\) has very high frequencies, which makes the problem hard to solve in practice. In general, it can be very challenging to find (the problem-dependent) value for \(\lambda\) that best balances the tradeoff between optimality and feasibility in the objective function [19]. For QAOA, a second approach is to define mixers that have zero probability to go from a feasible state to an infeasible one, making the hyperparameter \(\lambda\) of the previous approach unnecessary. However, it is generally more challenging to devise mixers that take into account constraints. The most prominent example in the literature is the _XY_-mixer [2; 18; 19], which constrains evolution to states with nonzero overlap with \"one-hot\" states. One-hot states are computational basis states with exactly one entry equal to one. For instance, \(|0001\rangle\) and \(|010000\rangle\) are one-hot states, while \(|00\rangle\) and \(|110\rangle\) are not. The name _XY_ mixer comes from the related _XY_-Hamiltonian [20]. The mixers derived in the literature follow the intuition of physicists to use \"hopping\" terms.