# 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 color parity mixers we now defined use the adjacent partial mixer. Other mixers, using more of the \({n\choose 2}^{2}\) partial mixers, are possible, as are repeated versions of the following color-parity ordering swap mixer. Color-parity ordering swap mixer.Simultaneous ordering swap mixer.To define the ordered partition, we first defined an ordered partition on the set of adjacent partial mixers \(U_{\text{PS},i,\{u,v\}}\) for a fixed tour position \(i\), where the parts of this partition contains mutually commuting partial mixers. We then partitioned the \(i\) to obtain a full ordered partition. Two partial mixers \(U_{\text{PS},i,\{u,v\}}\) and \(U_{\text{PS},i,\{u^{\prime},v^{\prime}\}}\) commute as long as \(\{u,v\}\cap\{u^{\prime},v^{\prime}\}=\emptyset\). Partitioning the \({n\choose 2}\) pairs of cities into \(\kappa\) parts such that each part contains only mutually disjoint pairs is equivalent to considering a \(\kappa\)-edge-coloring of the complete graph \(K_{n}\) and assigning an ordering to the colors. For odd \(n\), \(\kappa=n\) suffices, and for even \(n\), \(\kappa=n-1\) suffices [40]. (Using the geometrical construction based on regular polygons, we can define the canonical partition by placing the vertices at the vertices of the polygon in order, with the last one in the center for even \(n\); the parts of the partition are then ordered by their lowest element under the lexicographical ordering of the pairs of cities \(\{u,v\}\).) Let \(\mathcal{P}_{\text{col}}=\left(P_{1},\ldots,P_{c},\ldots,P_{\kappa}\right)\) be the resulting ordered partition, which we call a \"color partition\" of the pairs of cities. For example, for \(n=4\), the partition is \(\mathcal{P}_{\text{col}}=\left(\{\{1,2\},\{3,4\}\}\right),\{\{1,3\},\{2,4\}\}, \{\{1,4\},\{2,3\}\}\right)\). For different tour positions \(i\), two partial unitaries \(U_{\text{PS},i,\{u,v\}}\) and \(U_{\text{PS},i^{\prime},\{u^{\prime},v^{\prime}\}}\) commute if \(i\) and \(i^{\prime}\) are not consecutive (\(|i-i^{\prime}\mod n|>1\)). Thus, for partitioning the positions, we may use the parity partition \(\mathcal{P}_{\text{par}}\), as defined in Section 4.1. We can thus define the \"color-parity\" ordered partition \(\mathcal{P}_{\text{CP}}=\mathcal{P}_{\text{col}}\times\mathcal{P}_{\text{par}}\), with the induced lexicographical ordering of the parts. The part \(P_{c,\text{odd}}\) contains all \(U_{\text{PS},i,\{u,v\}}\) such that \(i\) is odd and edge \(\{u,v\}\) is colored \(c\), i.e., in \(P_{c}\), and defines the unitary:  
\[U_{c,\text{odd}}(\beta)=\prod_{(i,\{u,v\})\in P_{c,\text{odd}}}U_{\text{PS},i,\{u,v\}}(\beta), \tag{51}\]  
where the ordering of the products does not matter because each term commutes. It is a similar case for \(P_{c,\text{even}}\) and \(U_{c,\text{even}}\), and \(P_{c,\text{last}}\) and \(U_{c,\text{last}}\). Thus, we have the full color-parity mixer:  
\[U_{\text{CP}}(\beta)=U_{\mathcal{P}_{\text{CP}}\text{-PS}}(\beta)=\prod_{P_{c},\pi\in\mathcal{P}_{\text{CP}}}U_{c,\pi}, \tag{52}\]  
where the unitaries \(\{U_{c,\pi}\}\) are applied in the order they appear in \(\mathcal{P}_{\text{CP}}\). The color-parity partition is optimal with respect to the number of parts in the partition (exactly so for even \(n\) and up to an additive factor of 2 for odd \(n\)). By construction, application of this mixer to any feasible state results in a feasible state, thus satisfying the first design criterion. With regard to the second criterion, while a single application of this mixer will have nonzero transitions only between orderings that swap cities in tour positions no more than two apart, repeating the mixer sufficiently many times results in nonzero transitions between any two states representing orderings. More precisely, since any ordering can be obtained from any other with no more than \(\frac{n(n-1)}{2}\) adjacent swaps, alternating between odd and even swaps, \(\frac{n(n-1)}{2}\) repeats suffice for any \(0<\beta<\pi/2\).