# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 3 Construction of Constraint Preserving Mixers
### Conditions on the Mixer Hamiltonian
: _Statements in Theorem 1 that hold for a particular ordering of computational basis states for a given \(B\) hold also for any permutation \(\pi:\{1,\cdots,|J|\}\to\{1,\cdots,|J|\}\), i.e., they are independent of the ordering of elements. For each ordering, the transition matrix \(T\) changes according to \(T_{\pi}=P_{\pi}^{T}TP_{\pi}\), where \(P_{\pi}\) is the permutation matrix associated with \(\pi\)._  
Proof. : We start by pointing out that the inverse matrix of \(P_{\pi}\) exists and can be written as \(P_{\pi}^{-1}=P_{\pi^{-1}}=P_{\pi^{-1}}^{T}\). The resulting matrix \(H_{M}\) is unchanged. Following the derivation in Equation (14), we have that \(H_{M_{\pi}}=E_{\pi}T_{\pi}E_{\pi}^{T}\), where the columns of the matrix \(E\in\mathbb{R}^{2^{\pi}\times|J|}\) consist of the _permuted_ feasible computational basis states, i.e., \(E_{\pi}=\{x_{\pi(\bar{j})}\}_{j\in I}\). Inserting \(T=P_{\pi}^{T}TP_{\pi}\), we have indeed \(H_{M_{\pi}}=E_{\pi}T_{\pi}E_{\pi}^{T}=(E_{\pi}P_{\pi}^{T})T(P_{\pi}E_{\pi}^{T} )=ETE^{T}=H_{M}\). \(T_{\pi}\) is symmetric if \(T\) is. Assuming that \(T^{T}=T\), we have that also  
\[(T_{\pi})^{T}=(P_{\pi}^{T}TP_{\pi})^{T}=P_{\pi}^{T}T^{T}P_{\pi}=P_{\pi}^{T}TP_ {\pi}=T_{\pi}.\]  
If the condition in Equation (11) holds for \(T\), then it also holds for \(T_{\pi}\). Using \(T_{\pi}^{T}=P_{\pi}^{T}T^{T}P_{\pi}\), we can show that Equation (11) holds for the permuted index pair \((\pi(\bar{j}),\pi(k))\) for \(T_{\pi}\) if it holds for \((j,k)\) for \(T\). In the following, if nothing else is remarked, computational basis states are ordered with respect to increasing integer value, e.g., \(|001\rangle,|010\rangle,|111\rangle\). Apart from special cases, there is a lot of freedom to choose the transition matrix \(\mathrm{T}\) that fulfills the conditions of Theorem 1. The entries of \(\mathrm{T}\) will heavily influence the circuit complexity, which will be investigated in Section 3.3. In addition, we have the following property which adds additional flexibility to develop efficient mixers. **Corollary 2** (Properties of mixers). : _For a given feasible subspace \(\mathrm{Sp}(B)\), let \(U_{M,B}\) be the mixer given by Theorem 1. For any subspace \(\mathrm{Sp}(C)\) with \(\mathrm{Sp}(B)\cap\mathrm{Sp}(C)=\{0\}\) or equivalently \(B\cap C=\varnothing\), also \(U_{M}=U_{M,B}U_{M,C}\) is a valid mixer for \(B\) satisfying the conditions of Equations (5) and (6); see also Figure 2._  
Proof. : Any \(|v\rangle\in B\) is in the null space of \(H_{M,C}\), i.e., \(H_{M,C}|v\rangle=0\) and hence \(U_{M,C}|v\rangle=I\). Therefore, \(U_{M,B}U_{M,C}|v\rangle=U_{M,B}|v\rangle\in B\), and \(U_{M,C}U_{M,B}|v\rangle=U_{M,C}|w\rangle=|w\rangle\) with \(|w\rangle\in B\) which means the feasible subspace is preserved. Condition (6) follows similarly from the fact that \(U_{M,C}|v\rangle=I\) for any \(|v\rangle\in B\). Corollary 2 naturally holds as well for any linear combination of mixers, i.e., \(H_{M,B}+\sum_{i}a_{i}H_{M,C_{i}}\) is a mixer for the feasible subspace \(\mathrm{Sp}(B)\) as long as \(\mathrm{Sp}(C_{i})\cap\mathrm{Sp}(B)=\{0\},\forall i\). At first, it might sound counterintuitive that adding more terms to the mixer results in more efficient decomposition into basis gates. However, as we will see in Section 5, it can lead to cancellations due to symmetry considerations. Next, we describe the structure of the eigensystem of \(U_{M}\). Figure 2: Corollary 2 shows that adding a mixer with support outside \(\mathrm{Sp}(B)\) is also a valid mixer for \(B\). **Corollary 3** (Eigensystem of mixers). : _Given the setting in Theorem 1 with a symmetric transition matrix \(T\). Let \((\lambda,v)\) be an eigenpair of \(T\), then \((\lambda,Ev)\) is an eigenpair of \(H_{M}\) and \((e^{-it\lambda},Ev)\) is an eigenpair of \(U_{M}\), where \(E=\{\big{|}x_{j}^{\prime}\big{\rangle}\}_{j\in J}\) as defined in Equation (14)._  
Proof. : Let \((\lambda,v)\) be an eigenpair of \(T\). Then, \(H_{M}Ev=ETE^{T}Ev=ETv=\lambda Ev\), so \((\lambda,Ev)\) is an eigenpair of \(H_{M}\).