# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 5 QAOA Mappings: Orderings and Schedules
### SMS, Minimizing Total Tardiness
#### 5.3.1 Encoding and Mixer  
The configuration space is the set of orderings of the jobs; the domain is the same.  
Absolute and positional encodings. In the \"absolute\" encoding of the ordering \(\iota=(t_{1},\dots,t_{n})\), we assigned each item \(i\) a value \(s_{i}\in[0,h]\), where the \"horizon\" \(h\) is a parameter of the encodings, such that for all \(i<j\), \(s_{i_{i}}<s_{i_{j}}\). In certain cases, there will be an item-specific horizon \(h_{i}\) such that\(s_{i}\in[0,h_{i}]\). Note that in general, the relationship between encoded states and the orderings they encode is not injective, but it will be in the domains to which we apply it. Once the ordering \(\iota\) is encoded as a string \(\mathbf{s}(\iota)\in\times_{i=1}^{n}[0,h_{i}]\), the resulting string can be encoded using any of the string encodings previously introduced. We call the special case of the \"absolute\" encoding with \(h=n\) the \"positional\" encoding; using the one-hot encoding of the resulting strings, the \"direct\" and \"positional\" encodings are the same.  
Time-swap mixer. We now introduce a mixer that is specific to the absolute encoding in which there is a single horizon \(h\) and each job \(i\) has a processing time \(p_{i}\). Let the horizon be \(h=\sum_{i=1}^{n}p_{i}\). Each job can start between time \(0\) and \(h_{i}=h-p_{i}\). (Other optimizations may be made on an instance-specific basis, though we neglect elaborating on these for ease of exposition.) We used a \"time-swap\" partial mixer that acts on absolutely encoded orderings:  
\[H_{\text{TS},t,\{i,j\}}=\left|t+p_{j},t\right\rangle\left\langle t,t+p_{i} \right|_{i,j}+\left|t,t+p_{i}\right\rangle\left\langle t+p_{j},t\right|_{i,j}, \tag{63}\]  
which swaps jobs \(i\) and \(j\) when they are scheduled immediately after one another, with the earlier one starting at time \(t\). To swap them regardless of the time at which the earlier one starts, we used:  
\[H_{\text{TS},\{i,j\}}=\sum_{t=0}^{h-p_{i}-p_{j}}H_{\text{TS},t,\{i,j\}}. \tag{64}\]  
The _simultaneous_ time-swap mixer is constructed as usual:  
\[U_{\mathcal{P}\text{-TS}}(\beta)=e^{-i\beta H_{\text{TS}}}, \tag{65}\]  
where \(H_{\text{TS}}=\sum_{\{i,j\}\in\binom{[n]}{2}}H_{\text{TS},\{i,j\}}\). Note that while the simultaneous versions of the total time-swap and adjacent permutation mixers are exactly the same, and in particular:  
\[H_{\text{TS},\{i,i^{\prime}\}}=\sum_{j=1}^{n-1}H_{\text{PS},t,\{i,i^{\prime}\}}, \tag{66}\]  
the individual partial mixer \(H_{\text{TS},t,\{i,j\}}\) has no equivalent that acts on the unencoded ordering, because it acts depending on the total processing times of the preceding jobs rather than their number.  
Now consider the \"time-color\" ordered partition \(\mathcal{P}_{\text{TC}}=[0,h]\times[\kappa]\), where, as in Section 5.1.1, we used a particular \(\kappa\)-edge-coloring of the complete graph. (Again, further optimizations may be made on an instance-specific basis.) The partition \(P_{t,c}\) contains the partial time-swap mixers \(U_{\text{TS},t,\{i,j\}}\) for which the edge \(\{i,j\}\) is colored \(c\). The full \"time-color\" mixer is:  
\[U_{\text{TS}}(\beta)=\prod_{t=0}^{h}\prod_{c=1}^{\kappa}U_{(t,c)\text{-TS}}( \beta), \tag{67}\]  
where \(U_{(t,c)\text{-TS}}\) is the product of the (mutually commuting) partial mixers in the part \(P_{t,c}\).