# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 3 Construction of Constraint Preserving Mixers
### Trotterizations  
Algorithms 1 and 2 produce a weighted sum of Pauli-strings equal to the mixer Hamiltonian \(H_{M}\) defined in Theorem 1. A further complication arises when the non-vanishing Pauli-strings of the mixer Hamiltonian \(H_{M}\) do not all commute. In that case, one can not realize \(U_{M}\) exactly but has to find a suitable approximation/Trotterization; see Equation (32). Two Pauli-strings _commute_, i.e., \([P_{A},P_{B}]=P_{A}P_{B}-P_{B}P_{A}=0\) if, and only if, they _fail_ to commute on an _even_ number of indices [25]. An example is given in Figure 5.  
This problem is similar to a problem for observables: how does one divide the Pauli-strings into groups of commuting families [25; 26] to maximize efficiency and increase accuracy? In order to minimize the number of measurements required to estimate a given observable, one wants to find a \"min-commuting-partition\"; given a set of Pauli-strings from a Hamiltonian, one seeks to partition the strings into commuting families such that the total number of partitions is minimized. This problem is NP-hard in general [25]. However, based on Theorem 3, we expect our problem to be much more tractable. Figure 5: In the commutation graph (**middle**) of the terms of the mixer given in Equation (47), an edge occurs if the terms commute. From this, we can group terms into three (nodes connected by green edge) or two (nodes connected by red/blue edges) sets. Only the **left**/green grouping preserves the feasible subspace, the **right** one does not. For our case, it turns out that not all Trotterizations are suitable as mixing operators; they can either fail to preserve the feasible subspace, i.e., Equation (5), or fail to provide transitions between all pairs of feasible states, i.e., Equation (6). An example is given by \(B=\{|001\rangle,|010\rangle,|100\rangle\}\) with the mixer \(H_{M}=\frac{1}{2}(XIX+YY)+\frac{1}{2}(XXI+YYI)\) associated with \(T_{\Delta}=T_{1+2}+T_{2+3}\); see Section 5.1. Looking at Figure 5, these terms can be grouped into commuting families in two ways, which represent two (of many) different ways to realize the mixer unitary with basis gates. 1. The first possible Trotterization is given by \(U_{1}(\beta)=e^{-i\beta(XXI+IXX)}\) and \(U_{2}(\beta)=e^{-i\beta(YYI+YY)}\). However, it turns out that \(\exists\beta\in\mathbb{R}\) such that \(|\langle 111|U_{1}(\beta)U_{2}(\beta)|z\rangle|>0\) for all \(|z\rangle\in B\). This means that this Trotterization does _not preserve the feasible subspace_ and does not represent a valid mixer Hamiltonian. The underlying reason for this is that the terms \(XXI\) and \(YYI\) are generated from the entry \(T_{1\leftrightarrow 2}\), but are split in this Trotterization. The same holds true for \(IXX\) and \(YYY\), which are generated via \(T_{2\leftrightarrow 3}\). 2. The second possible Trotterization is given by \(U_{1}(\beta)=e^{-i\beta(XXI+YYI)}\) and \(U_{2}(\beta)=e^{-i\beta(XXI+YYI)}\), which splits terms with respect to \(T_{1\leftrightarrow 2}\) and \(T_{2\leftrightarrow 3}\) In this case, we have that \(|\langle 100|U_{1}(\beta)U_{2}(\beta)|001\rangle|=0\), so it does _not provide an overlap_ between all feasible computational basis states. This can be understood via Theorem 2. We have that \((T_{1\leftrightarrow 2}^{n_{1}}T_{2\leftrightarrow 3}^{n_{2}})_{3,1}=0\) for all \(n_{1},n_{2}\in\mathbb{N}\), so one can not \"reach\" \(|100\rangle\) from \(|001\rangle\). The opposite is _not_ true; we have that \((T_{1\leftrightarrow 2}T_{2\leftrightarrow 3})_{1,3}=1\), so \(\exists\beta\) such that \(|\langle 001|U_{1}(\beta)U_{2}(\beta)|\)\(|100\rangle|>0\). We have just learned that it is a bad idea to Trotterize terms that belong to a nonzero entry of T, i.e., to \(T_{j\leftrightarrow i}\). Therefore, we need to show that all non-vanishing Pauli-strings of \(\left|x_{j}\right\rangle\left\langle x_{i}\right|+\left|x_{i}\right\rangle \left\langle x_{j}\right|\) commute; otherwise, there might exist subspaces for which we can not realize the mixer constructed in Theorem 1.