# Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm
## 3 Construction of Constraint Preserving Mixers
### Decomposition of (Constraint) Mixers into Basis Gates  
Given a set of feasible (computational basis) states \(B=\left\{|x_{j}\rangle,\ \ j\in J,\ \ x_{j}\in\{0,1\}^{n}\right\}\), we can use Theorem 1 to define a suitable mixer Hamiltonian. The next question is how to (efficiently) decompose the resulting mixer into basis gates. In order to do so, we first decompose the Hamiltonian \(H_{M}\) into a weighted sum of Pauli-strings. A Pauli-string \(P\) is a Hermitian operator of the form \(P=P_{1}\otimes\cdots\otimes P_{n}\) where \(P_{i}\in\{I,X,Y,Z\}\). Pauli-strings form a basis of the _real_ vector space of all \(n\)-qubit Hermitian operators. Therefore, we can write  
\[H_{M}=\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{31}\]with real coefficients \(c_{i_{1},\cdots,i_{n}}\), where \(\sigma_{1}=I,\sigma_{2}=X,\sigma_{3}=Y,\sigma_{4}=Z\). After using a standard Trotterization scheme [4; 5] (which is exact for commuting Pauli-strings),  
\[U_{M}(\text{f})=e^{-itH_{M}}\approx\prod_{ \begin{subarray}{c}i_{1},\cdots,i_{ n}=1\\ |i_{1},\cdots,i_{n}|>0\end{subarray} }^{4}e^{-itc_{i_{1},\cdots,i_{n}}\,\sigma_{i_{1} }\otimes\cdots\otimes\sigma_{i_{n}}}, \tag{32}\]  
it is well-established how to implement each of the terms of the product using basis gates; see Equation (33). We will discuss the effects of Trotterization in more detail in Section 3.5, as there are several important aspects to consider for a valid mixer. (33)  
Here, \(S\) is the S or Phase gate and \(H\) is the Hadamard gate. The standard way to compute the coefficients \(c_{i_{1},\cdots,i_{n}}\) is given in Algorithm 1. ```
Data: Feasible states \(B\) and transition matrix \(\mathbb{T}\) fulfilling Theorem 1 Result: Coefficients \(c_{i_{1},\cdots,i_{n}}\) of Pauli-strings, Equation (31) for\(i_{1}=1,\ldots,4\)do \(\ddots\) for\(i_{n}=1,\ldots,4\)do \(c_{i_{1},\cdots,i_{n}}=\frac{1}{2^{n}}\operatorname{Tr}\sigma_{i_{1}}\otimes \cdots\otimes\sigma_{i_{n}}H_{M}\)  end \(\therefore\) end
```  
**Algorithm 1**Decompose \(H_{M}\) given by Equation (10) into Pauli-strings via trace  
For \(n\) qubits, this requires to compute \(4^{n}\) coefficients, as well as the multiplication of \(2^{n}\times 2^{n}\) matrices. However, most of these terms are expected to vanish. We therefore describe an alternative way to produce this decomposition, using the language of quantum mechanics [24]. In the following, we use the _ladder operators_ used in the creation and annihilation operators from the second quantization formulation in quantum chemistry defined by  
\[a^{\dagger}=\frac{1}{2}(X-iY),a=\frac{1}{2}(X+iY). \tag{34}\]  
Since \(a|0\rangle=0,a|1\rangle=|0\rangle\), where \(0\) is the zero vector, we have that \(|0\rangle\langle 1|=a\). Since \(a^{\dagger}|0\rangle=|1\rangle,a^{\dagger}|1\rangle=0\), we have that \(|1\rangle\langle 0|=a^{\dagger}\), and finally \(a^{\dagger}a|0\rangle=0,a^{\dagger}a|1\rangle=|1\rangle,aa^{\dagger}|0\rangle=|0\rangle, a\,a^{\dagger}|1\rangle=0\), means that \(|0\rangle\langle 0|=aa^{\dagger}\) and \(|1\rangle\langle 1|=a^{\dagger}a\). Note that  
\[a^{\dagger}a=\frac{1}{2}(I-Z),\quad aa^{\dagger}=\frac{1}{2}(I+Z). \tag{35}\]As an example, consider the matrix \(M=|01\rangle\langle 10|=|0\rangle\langle 1|\otimes|1\rangle\langle 0|\), which can be expressed with ladder operators as \(M=a_{1}a_{2}^{\intercal}\). Another example is given by \(M=|01\rangle\langle 11|=a_{1}a_{2}^{\intercal}a_{2}\). This approach clearly extends to the general case and leads to Algorithm 2. ```
Data: Feasible states \(B\) and transition matrix T fulfilling Theorem 1 Result: Non-vanishing coefficients \(c_{i_{1},\cdots,i_{n}}\) of Pauli-strings, Equation (31) S=0 for all\(1\leq j,k\leq|J|\), s.t. \((T)_{j,k}\
eq 0\)do  Define \(x_{L}=x_{j,r}x_{R}=x_{l}\) for\(1\leq i\leq n\)do \((P_{j,k})_{i}=