# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 1 Introduction  
The quantum approximate optimization algorithm (QAOA) [1], and its generalization, the quantum alternating operator ansatz (also abbreviated as QAOA) [2], is a meta-heuristic for solving combinatorial optimization problems that can utilize gate-based quantum computers and possibly outperform purely classical heuristic algorithms. Typical examples that can be tackled are quadratic (binary) optimization problems of the form  
\[x^{*}=\operatorname*{arg\,min}_{x\in\{0,1\}^{n},~{}g(x)=0}f(x),\quad f(x)=x^{T }Q_{f}x+c_{f},\quad g(x)=x^{T}Q_{g}x+c_{g} \tag{1}\]  
where \(Q_{f},Q_{g}\in\mathbb{R}^{n\times n}\) are symmetric \(n\times n\) matrices. For binary variables \(x\in\{0,1\}\), any linear part can be absorbed into the diagonal of \(Q_{f}\) and \(Q_{g}\). In this article, we focus on the case where the constraint is given by a feasible subspace as defined in the following:  
**Definition 1** (Constraints given by indexed computational basis states). : _Let \(\mathcal{H}=(\mathcal{C}^{2})^{\oplus n}\) be the Hilbert space for \(n\) qubits, which is spanned by all computational basis states \(|z_{j}\rangle\), i.e., \(\mathcal{H}=\operatorname{span}\{|z_{j}\rangle,1\leq j\leq 2^{n},z_{j}\in\{0,1\}^{n}\}\). Let_  
\[B=\left\{|z_{j}\rangle,~{}~{}j\in J,~{}~{}z_{j}\in\{0,1\}^{n}\right\}, \tag{2}\]  
_be the subset of all computational basis states defined by an index set \(J\). This corresponds to_  
\[g(x)=\prod_{j\in J}\sum_{i=1}^{n}\bigl{(}x_{i}-(z_{j})_{i}\bigr{)}^{2}, \tag{3}\]_which is a quadratic constraint._  
There is a well-established connection of quadratic (binary) optimization problems to Ising models, see, e.g., [3], that allows one to directly translate these problems to the QAOA. The general form of QAOA is given by  
\[|\gamma,\beta\rangle=U_{M}(\beta_{p})U_{P}(\gamma_{p})\cdots U_{M}(\beta_{1})U_{ P}(\gamma_{1})|\phi_{0}\rangle, \tag{4}\]  
where one alternates the application of phase separating and mixing operator \(p\) times. Here, \(U_{P}(\gamma)\) is a phase separating operator that depends on the objective function \(f\). As defined in [2], the requirements for the mixing operator \(U_{M}(\beta)\) are as follows  
* \(U_{M}\) does not commute with \(U_{P}\), i.e., \([U_{M}(\beta),U_{P}(\gamma)]\
eq 0\), for almost all \(\gamma,\beta\in\mathbb{R}\);
* \(U_{M}\)_preserves the feasible subspace_ as given in Definition 1, i.e., \(\text{Sp}(B)\) is an invariant subspace of \(U_{M}\), \[U_{M}(\beta)|v\rangle\in\text{Sp}(B),\quad\forall|v\rangle\in\text{Sp}(B), \forall\beta\in\mathbb{R};\] (5)
* \(U_{M}\) provides transitions between all pairs of feasible states, i.e., for each pair \(x,y\)\(\exists\beta^{*}\in\mathbb{R}\) and \(\exists r\in\mathbb{N}\cap\{0\}\), such that \[|\langle x|\underbrace{U_{M}(\beta^{*})\cdots U_{M}(\beta^{*})}_{r\text{ times}}|y\rangle|>0,\forall\text{ comp. basis states }|x\rangle,|y\rangle\in B.\] (6)  
If both \(U_{M}\) and \(U_{P}\) correspond to the time evolution under some Hamiltonians \(H_{M},H_{P}\), i.e., \(U_{M}=e^{-i\beta H_{M}}\) and \(U_{P}=e^{-i\gamma H_{P}}\), the approach can be termed \"Hamiltonian-based QAOA\" (H-QAOA). If the Hamiltonians \(H_{M},H_{P}\) are the sum of (polynomially many) local terms, it represents a sub-class termed \"local Hamiltonian-based QAOA\" (LH-QAOA). In practice, it is not possible to implement \(U_{M}\) or \(U_{P}\) directly. It is necessary to decompose the evolution into smaller pieces, which means that instead of applying \(e^{-it(H_{1}+H_{2})}\), one can only apply \(e^{-itH_{1}}\) and \(e^{-itH_{2}}\). This process is typically referred to as _\"Trotterization\"_. As an example, the simplest Suzuki-Trotter decomposition, or the exponential product formula [4; 5] is given by  
\[e^{x(H_{1}+H_{2})}=e^{xH_{1}}e^{xH_{2}}+\mathcal{O}(x^{2}) \tag{7}\]  
where \(x\) is a parameter and \(H_{1},H_{2}\) are two operators with some commutation relation \([H_{1},H_{2}]\
eq 0\). Higher-order formulas can be found for instance in [4].