# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 3 Construction of Constraint Preserving Mixers
### Conditions on the Mixer Hamiltonian  
**Theorem 1** (Mixer Hamiltonians for subspaces). : _Given a feasible subspace \(B\) as in Definition 1 and a real-valued transition matrix \(T\in\mathbb{R}^{|\left|\right|\times\left|\right|}\). Then, for the mixer constructed via_  
\[U_{M}(\beta)=e^{-i\beta H_{M}},\quad\text{where }H_{M}=\sum_{j,k\in J}(T)_{ j,k}|x_{j}\rangle\langle x_{k}|, \tag{10}\]  
_the following statements hold._  
* _If_ \(T\) _is symmetric, the mixer is well defined and preserves the feasible subspace, i.e., condition (_5_) is fulfilled._
* _If_ \(T\) _is symmetric and for all_ \(1\leq j,k\leq|J|\)_, there exists an_ \(r\in\mathbb{N}\cup\{0\}\) _(possibly depending on the pair) such that_ \[(T^{r})_{j,k}\
eq 0,\] (11) _then_ \(U_{M}\) _provides transitions between all pairs of feasible states, i.e., condition (_6_) is fulfilled._  
Proof. : Well definedness. Almost trivially \(H_{M}\) is Hermitian if \(T\) is symmetric,  
\[H_{M}^{\dagger}=\sum_{j,k\in J}(T)_{j,k}|x_{k}\rangle\langle x_{j}|=\sum_{j,k \in J}(T)_{k,j}|x_{k}\rangle\langle x_{j}|=H_{M}. \tag{12}\]  
Since \(H_{M}\) is a Hermitian (and therefore normal) matrix, there exists a diagonal matrix \(D\), with the entries of the diagonal as the (real valued) eigenvalues of \(H_{M}\), and a matrix \(U\), with columns given by the corresponding orthonormal eigenvectors. The mixer is therefore well defined through the convergent series  
\[e^{-itH_{M}}=\sum_{m=0}^{\infty}\frac{(-it)^{m}H_{M}^{m}}{m!}=Ue^{-itD}U^{ \dagger}. \tag{13}\]  
Reformulations. We can rewrite \(H_{M}\) in the following way  
\[H_{M}:\ \ |y\rangle\mapsto\sum_{j,k\in J}(T)_{j,k}\langle\alpha_{j}|y\rangle| x_{k}\rangle=ETE^{T}|y\rangle,\ \ |y\rangle\in\mathcal{C}^{2^{m}}, \tag{14}\]where the columns of the matrix \(E\in\mathbb{R}^{2^{n}\times|I|}\) consist of the feasible computational basis states, i.e., \(E=[x_{j}]_{j\in J}\); see Figure 1 for an illustration. Using that \(E^{T}E=I\in\mathbb{R}^{|I|\times|J|}\) is the identity matrix, we have that  
\[H_{M}^{m}=ET^{m}E^{T}=\sum_{j,k\in J}(T^{m})_{j,k}|x_{j}\rangle\langle x_{k}|, \ m\in\mathbb{N}, \tag{15}\]  
and Equation (13) can be written as  
\[e^{-itH_{M}}=E\bigg{(}\sum_{m=0}^{\infty}\frac{(-it)^{m}T^{m}}{m!}\bigg{)}E^{T}. \tag{16}\]  
Preservation of the feasible subspace. Let \(|v\rangle\in\text{Sp}(B)\). Using Equation (15), we know that  
\[H_{M}^{m}|v\rangle=\sum_{j,k\in J}(T^{m})_{j,k}|x_{j}\rangle\langle x_{k}|v \rangle=\sum_{j\in J}c_{j}|x_{j}\rangle\in\text{Sp}(B),\]  
with coefficients \(c_{j}\in\mathcal{C}\). Therefore, also \(e^{-itH_{M}}|v\rangle\in\text{Sp}(B),t\in\mathbb{R}\), since it is a sum of these terms. Transition between all pairs of feasible states. For any pair of feasible computational basis states \(\big{|}x_{j^{\prime}}\big{>},|x_{k^{*}}\rangle\in B\), we have that  
\[ \begin{split} f(t)&=\big{\langle}x_{j^{\prime}} \big{|}U_{M}(t)|x_{k^{*}}\rangle=\big{\langle}x_{j^{\prime}}\big{|}\sum_{m=0}^ {\infty}\left(\frac{(-it)^{m}}{m!}\sum_{j,k\in I}(T^{m})_{j,k}|x_{j}\rangle \langle x_{k}|\right)|x_{k^{*}}\rangle\\ &=\sum_{m=0}^{\infty}\frac{(-it)^{m}}{m!}(T^{m})_{j^{\prime},k^{ *}}\end{split}  \tag{17}\]  
It is enough to show that \(f(t)\) is not the zero function. Since \(f(t):\mathbb{R}\rightarrow\mathcal{C}\) is an analytic function, it has a unique extension to \(\mathcal{C}\). Assume that \(f\) is indeed the zero function on \(\mathbb{R}\); then, the extension to \(\mathcal{C}\) would also be the zero function, and all coefficients of its Taylor series would be zero. However, we assumed the existence of an \(r\in\mathbb{N}\cup\{0\}\) such that \(|(T^{r})_{j^{\prime},k^{*}}|>0\), and hence, there exists a nonzero coefficient, which is a contradiction to \(f\) being the zero function. A natural question is how the statements in Theorem 1 depend on the particular ordering of the elements of \(B\). Figure 1: Illustration of properties of Hamiltonians constructed with Theorem 1. **Corollary 1** (Independence of the ordering of \(B\)).