# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 3 Construction of Constraint Preserving Mixers
### Trotterizations
Luckily, the following theorem shows that it is always possible to realize a mixer by Trotterizing according to nonzero entries of \(T=\sum_{i,j\in j<i}T_{j\leftrightarrow i}\). **Theorem 3** (Pauli-strings for \(T_{j\leftrightarrow i}\) commute). : _Let \(|z\rangle,|w\rangle\) be two computational basis states in \(\mathcal{C}^{2\pi}\). Then, all non-vanishing Pauli-strings \(\sigma_{i_{1}}\otimes\cdots\otimes\sigma_{i_{n}}\) of the decomposition_  
\[|z\rangle\langle w|+|w\rangle\langle z|=\sum_{i_{1},\cdots,i_{n}=1}^{4}c_{i_{ 1},\cdots,i_{n}}\ \sigma_{i_{1}}\otimes\cdots\otimes\sigma_{i_{n}},\quad c_{i_{1},\cdots,i_{n}} \in\mathbb{R}, \tag{37}\]  
_commute._  
Proof. : We will prove the following more general assertion by induction. Let \(P_{1+1},P_{1+2}\) be two non-vanishing Pauli-strings of the decomposition of \(|z\rangle\langle w|+|w\rangle\langle z|\), and \(P_{i-1},P_{i-2}\), be two non-vanishing Pauli-strings of the decomposition of \(i(|z\rangle\langle w|-|w\rangle\langle z|)\). Then, \([P_{1+1},P_{1+2}]=0\), \([P_{i-1},P_{i-2}]=0\) and \([P_{1+\cdot},P_{i-2}]\
eq 0\). We will use that two Pauli-strings commute if, and only if, they _fail_ to commute on an _even_ number of indices [25]. For \(n=1\), we have the following cases. \[A_{1}=\left|z\rangle\langle w|+|w\rangle\langle z|= \begin{cases}I+Z,\text{ if }(z,w)=(0,0),\\ X,\text{ \ \ \ \ \ \ if}(z,w)=(0,1),\\ X,\text{ \ \ \ \ \ \ \ \ if}(z,w)=(1,0),\\ I-Z,\text{ if }(z,w)=(1,1),\end{cases} \ B_{1}=i(|z\rangle\langle w|-|w\rangle \langle z|)= \begin{cases}0,\text{ \ \ \ if}(z,w)=(0,0),\\ -Y,\text{ if}(z,w)=(0,1),\\ +Y,\text{ if}(z,w)=(1,0),\\ 0,\text{ \ \ \ \ \ if}(z,w)=(1,1).\end{cases}  \tag{38}\]  
It is trivially true that \([P_{1+1},P_{1+2}]=0\) and \([P_{i-1},P_{i-2}]=0\), since the maximum number of Pauli-strings is two, and in that case, one of the Pauli-strings is the identity. Moreover, \(P_{i-\cdot}\) is nonzero only when \(z\
eq w\). In that case, \([P_{1+\cdot},P_{i-\cdot}]=[X,\pm Y]\
eq 0\). \(n\to n+1\). We assume the assumptions hold for two computational basis states \(|z\rangle,|\overline{w}\rangle\in\mathcal{C}^{2^{n}}\). Then, there are the following four cases  
\[A_{n+1}=|wx\rangle\langle zy|+|wx\rangle\langle zy|= \frac{1}{2} \begin{cases}A_{n}\otimes(I+Z),&\text{if }(x,y)=(0,0),\\ A_{n}\otimes X+B_{n}\otimes Y,&\text{if }(x,y)=(0,1),\\ A_{n}\otimes X-B_{n}\otimes Y,&\text{if }(x,y)=(1,0),\\ A_{n}\otimes(I-Z),&\text{if }(x,y)=(1,1),\end{cases}  \tag{39}\] \[B_{n+1}=i(|wx\rangle\langle zy|-|wx\rangle\langle zy|)= \frac{1}{2} \begin{cases}0,&\text{if }(x,y)=(0,0),\\ B_{n}\otimes X-A_{n}\otimes Y,&\text{if }(x,y)=(0,1),\\ B_{n}\otimes X+A_{n}\otimes Y,&\text{if }(x,y)=(1,0),\\ 0,&\text{if }(x,y)=(1,1),\end{cases} \]  
where \(A_{n}=(|z\rangle\langle w|+|w\rangle\langle z|),B_{n}=i(|z\rangle\langle w|-|w \rangle\langle z|)\). Case \(x=y\). According to our assumptions that all non-vanishing Pauli-strings for \(A_{n}\) commute, the same holds for \(A_{n+1}=A_{n}\otimes(I\pm Z)\). Since \(B_{n+1}=0\), the rest of the assertions are trivially true, as there are no non-vanishing Pauli-strings. Case \(x\
eq y\). Our assumptions mean that non-vanishing Pauli-strings of \(A_{n}\) fail to commute on an odd number of indices with non-vanishing Pauli-strings of \(B_{n}\). Therefore, non-vanishing Pauli-strings of \(A_{n+1}=A_{n}\otimes X\pm B_{n}\otimes Y\) fail to commute on an even number of indices, and, hence, commute. The same argument holds for \(B_{n+1}=B_{n}\otimes X\pm A_{n}\otimes Y\). Finally, we prove that non-vanishing Pauli-strings of \(A_{n+1}\) and \(B_{n+1}\) do not commute. Either Pauli strings \(P_{1+,}\) and \(P_{i-,}\) stem from \(A_{n}\otimes X\) and \(B_{n}\otimes X\), respectively, or they stem from \(\pm A_{n}\otimes Y\) and \(\mp B_{n}\otimes Y\), respectively. In both cases, the number of commuting terms does not change, so non-vanishing Pauli-strings of \(A_{n+1}\) and \(B_{n+1}\) do not commute. The proof in Theorem 3.2 inspires the following algorithm to decompose \(H_{M}\) into Pauli-strings.