# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 5 QAOA Mappings: Orderings and Schedules
### Example: Traveling Salesperson Problem (TSP)
#### 5.1.1 Mapping  
The configuration space here is the set of all orderings of the cities. Labeling the cities by \(\left[n\right]\), the ordering \(\iota=\left({{{i_{1}},{{i_{2}},\ldots,{{i_{n-1}},{{i_{n}}}}}}}\right)\) indicates traveling from city \({{{i_{1}}}}\) to city \({{{i_{2}}}}\), then on to city \({{{i_{3}}}}\) and so on until finally returning from city \({{{i_{n}}}}\) back to city \({{{i_{1}}}}\). The configuration space includes some degeneracy in solutions with respect to cyclic permutations; specifically, for any ordering \(\iota\), the configuration space includes both \(\left({{{i_{1}},{{i_{2}},\ldots,{{i_{n-1}},{{i_{n}}}}}}}\right)\) and \(\left({{{i_{2}},{{i_{3}},\ldots,{{i_{n}},{{i_{1}}}}}}}\right)\), even though they are essentially the same solution to the TSP. We leave in this degeneracy in the constructions of this section in order to preserve symmetries which make it simpler to construct and present our mixers. Note that, in practice, this degeneracy may be removed by fixing a particular city as the starting point, resulting in an \(n-1\) city problem wit slightly simpler cost functions that yields the same solutions, for which it is straightforward to adapt the constructions below. As there are no problem constraints, the domain is the same as the configuration space. The objective function is:  
\[f(\iota)=\sum_{j=1}^{n}d_{{{i_{j}}}{{j_{j+1}}}}, \tag{45}\]  
where we again and throughout employed the convention \({{{i_{n+1}}}}:={{{i_{1}}}}\). Ordering swap partial mixing HamiltoniansOur mixers for orderings will be built from partial mixer Hamiltonians we call \"value-selective ordering swap mixing Hamiltonians.\" Consider \(\left\{{{{i_{l}},{{i_{j}}}}}\right\}=\left\{{{{u},{v}}}\right\}\), indicating that city \(u\) (resp. \(v\)) is visited at the \(i\)th (resp. \(j\)th) stop on the tour, or vice versa. There are \(\binom{n}{2}^{2}\) value-selective ordering swap mixing Hamiltonians, \(H_{\text{PS},\left\{{{i_{l}}}\right\},\left\{{{u},{v}}\right\}}\), which swap the \(i\)th and \(j\)th elements in the ordering if and only if those elements are the cities \(u\) and \(v\):  
\[ \begin{split}& H_{\text{PS},\left\{{{i_{l}}}\right\},\left\{{{u },{v}}\right\}}\\ &=\sum_{\iota:\left\{{{i_{l}}}\right\}=\left\{{{u},{v}}\right\}} \left|\left({{{i_{1}},\ldots,{{i_{i-1}},{{v}},\ldots{{i_{j-1}},{{\widehat{u_{i }}}}},\ldots{{i_{n}}}}}}\right)\right\rangle\left\langle\left({{{i_{1}},\ldots,{ {i_{i-1}}},{{u}},\ldots{{i_{j-1}}},{{v}},\ldots{{i_{n}}}}}}\right)\right|\.\end{split}  \tag{46}\]  
We made extensive use of a special case, the _adjacent_ ordering swap mixing Hamiltonians:  
\[H_{\text{PS},{{i_{l}}},\left\{{{u},{v}}\right\}}=H_{\text{PS},\left\{{{i_{l}} }+1\right\},\left\{{{u},{v}}\right\}}. \tag{47}\]  
To swap the \(i\)th and \(j\)th elements of the ordering regardless of which cities those are, we used the value-independent ordering swap partial mixing Hamiltonian:  
\[H_{\text{PS},\left\{{{i_{l}}}\right\}}=\sum_{\left\{{{u},{v}}\right\}\in \binom{\left[n\right]}{2}}H_{\text{PS},\left\{{{i_{l}}}\right\},\left\{{{u},{v} }\right\}}. \tag{48}\]Of these \({n\choose 2}\) partial mixing Hamiltonians, \(n\) are adjacent value-independent ordering swap partial mixing Hamiltonians:  
\[H_{\text{PS},i}=\sum_{t}\left|\left(t_{1},\ldots t_{i-1},t_{i+1},t_{i},t_{i+2}, \ldots,t_{n}\right)\right\rangle\left\langle\left(t_{1},\ldots,t_{n}\right) \right|, \tag{49}\]  
which swap the \(i\)th element with the subsequent one regardless of which cities those are. These partial mixers can be combined in several ways to form full mixers, of which we explore two types. Simultaneous ordering swap mixer.Defining \(H_{\text{PS}}=\sum_{i=1}^{n}H_{\text{PS},i}\), we have the \"simultaneous ordering swap mixer\":  
\[U_{\text{sim-PS}}(\beta)=e^{-i\beta H_{\text{PS}}}. \tag{50}\]  
Different subsets and partitions of the partial mixers \(U_{\text{PS},\{i,j\},\{u,v\}}=e^{-iH_{\text{PS},\{i,j\},\{u,v\}}}\) and different orderings of a partition yield different partitioned ordering swap mixers.