# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## Appendix A Compendium of Mappings and Compilations
### Permutation Mixers
#### a.5.2 SMS, Minimizing Total Weighted Squared Tardiness [Section 5.2]  
**Problem:**\((1|d_{j}|\sum w_{j}T_{j}^{2})\). Given a set of jobs with processing times \(\mathbf{p}\), deadlines \(\mathbf{d}\in\mathbb{Z}_{+}\), and weights \(\mathbf{w}\), find a schedule that minimizes the total weighted squared tardiness \(\sum_{j=1}^{n}w_{j}T_{j}^{2}\). **Approximability:** Considered in Reference [89]. **Configuration space and domain:** Orderings of the jobs \(\{\mathbf{i}\}\), and an integer slack variable \(y_{j}\in[0,d_{j}-p_{j}]\) for each job. **Objective:**\(\min f(\iota,\mathbf{y})=\sum_{j=1}^{n}w_{j}\big{(}s_{j}(\iota)+p_{j}-d_{j}+y_{j} \big{)}^{2}\). **Partial mixer:** Partial permutation swap mixer for computational qubits; binary mixer mixer for the slack qubits. **Encoding:** Direct one-hot for the ordering variables; binary for the slack variables. **Compilation:**  
\(\bullet\) **Phase separator:** The encoded phase separator is a 3-local Hamiltonian containing  
\(\bullet\)  all 1-local terms;  
\(\bullet\)  all 2-local terms of two computational qubits corresponding to different jobs at different places in the ordering, all 2-local terms of two ancilla qubits corresponding to the same job, and all 2-local terms of one computational qubit and one ancilla qubit except when they correspond to different jobs and the computational qubit corresponds to that job being last in the ordering;  
\(\bullet\)  all 3-local terms of three computational qubits corresponding to different jobs at different places in the ordering and all 3-local terms containing two computational qubits corresponding to different jobs at different places in the ordering and one ancilla qubit corresponding to the later job. \(\bullet\) **Partial mixer:**\(H_{\text{PS},\{i,j\},\{u,v\}}^{\text{(enc)}}=S_{u,i}^{+}S_{v,j}^{+}S_{u,j}^{-}S_{v,j}^{-}+S_{u,j}^{-}S_{u,j}^{ -}S_{u,j}^{+}S_{v,j}^{+}\). \(\bullet\) **Initial state** Arbitrary ordering. **Resource count:**  
* **Color-parity permutation swap mixer (Section 5.1):** At most \((n-1){n\choose 2}\) 4-qubit partial mixers, in depth at most \(2n\). Single-qubit \(X\) mixer for slack binary variables can be done in parallel with the permutation swap mixer. * **Phase separator:** Let \(\mu_{i}=\lceil\log_{2}(d_{i}-p_{i}+1)\rceil\) be the number of bits needed for the slack variable \(y_{i}\), and \(\mu=\sum_{i=1}^{n}\mu_{i}\). **-** Number of 1-local gates: \(n^{2}+\mu\). **-** Number of 2-local gates: \(2{n\choose 2}^{2}+\sum_{i=1}^{n}{(\mu_{i}^{k})}+\mu(n^{2}-n+1)\). **-** Number of 3-local gates: \(6{n\choose 3}^{2}+2\mu{n\choose 2}^{2}\). * **Initial state:**\(n\) single-qubit \(X\) gates. Depth 1. **Appendix A.5.3**. : SMS, Minimizing Total Weighted Tardiness [Section 5.3]  
**Problem:**\((1|d_{j}|\sum w_{j}T_{j})\). Given a set of \(n\) jobs with processing times \(\mathbf{p}\), deadlines \(\mathbf{d}\in\mathbb{Z}_{+}\), and weights \(\mathbf{w}\), find a schedule that minimizes the total weighted tardiness \(\sum_{j=1}^{n}w_{j}T_{j}\). **Approximability:** There exists an \((n-1)\)-approximation [90]. The decision version is strongly NP-hard [91]. **Configuration space and domain:** Orderings of the jobs \(\{\mathbf{i}\}\). **Objective:**\(f(\iota)=\sum_{i=1}^{n}w_{i}\max\{0,d_{i}-s_{i}(\iota)-p_{i}\}\). **Encoding:** Absolute one-hot. **Mixing rule:** Swap two jobs only if they are scheduled in consecutive order. **Partial mixer:** Partial time-swap mixer (specific to the absolute encoding). **Initial state:** Arbitrary ordering. **Compilation:**  
* **Phase separator:**\(H_{\mathbf{p}}^{(\text{enc})}=\sum_{i=1}^{n}w_{i}\sum_{t=d_{i}-p_{i}+1}^{h_{ i}}(t+p_{i}-d_{i})Z_{i,t}\). * **Partial mixer:**\(H_{\mathbf{TS},\iota,\{i,j\}}^{(\text{enc})}=S_{i,t+p_{j}}^{+}S_{j,t}^{+}S_{i,t}^{-}S_{j,t}^{ -}+S_{i,t+p_{j}}^{-}S_{j,t}^{+}S_{j,t+p_{j}}^{+}\). **Resource count:**  
* **Color-time partitioned time-swap mixer:**\(h{n\choose 2}\) 4-qubit gates in depth \(h\kappa\). * **Phase separator:** At most \(nh\) single-qubit gates, depth 1. * **Initial state:**\(n\) single-qubit \(X\) gates, depth 1.