From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

We focused initially on designing partial mixers, component operators that will be used to construct full mixing operators. For this mapping of the maxColorableSubgraph problem, the partial mixers are operators acting on a qudit with dimension $d=\kappa$ that mix between the colors associated to a single vertex v. As we see in subsequent sections, this is a particularly simple case of partial mixers which are often more complicated multiqubit-controlled operators. Once we have defined these single-qudit partial mixing operators, we put them together to create a full mixer for the problem.

We began by considering the following family of single-qudit mixing operators expressed in terms of qudits, and qudit operators, and then considered encodings and compilations to qubit-based architectures, which inspired us to consider other families of single-qubit mixing operators. See Appendix C.2 and References [36,37] for a review of qudit operators, including the generalized Pauli operators $\breve{X}$ and $\breve{Z}$.

r-nearby-values single-qudit mixer. Let $U_{r-\mathrm{NV}}(\beta )=e^{-i\beta H_{r-\mathrm{NV}}}$, where $H_{r-\mathrm{NV}}={\sum }_{i=1}^r\left({\breve{X}}^i+{({\breve{X}}^{†})}^i\right)$, which acts on a single qudit, with $\breve{X}={\sum }_{a=0}^{d-1}|a+1\rangle \langle a|$. We identified two special cases by name: The “single-qudit ring mixer” for $r=1$, $H_{\mathrm{ring}}=H_{1-\mathrm{NV}}$ and the “fully-connected” mixer for $r=d-1$, $H_{\mathrm{FC}}=H_{(d-1)-\mathrm{NV}}$. Whenever we introduced a Hamiltonian, we also implicitly introduced its corresponding family of unitaries, as with $H_{r-\mathrm{NV}}$ and $U_{r-\mathrm{NV}}(\beta )$.

The single-qudit ring mixer is a cornerstone of many of the mixing constructions that we discuss. We concentrated on qubit encodings thereof, given the various projections of hardware with at least 40 qubits that will be available in the next year or two [11,12], though it could alternatively be implemented directly using a qudit-based architecture. We explored two natural encodings of a qudit into qubits: (1) The one-hot encoding using d qubits, in which each qudit basis state $|a\rangle$, $a=0,1,\dots ,d-1$, is encoded as ${|0\rangle }^{\otimes a}\otimes |1\rangle \otimes {|0\rangle }^{\otimes d-1-a}$; and (2) the binary encoding using $\lceil {log}_{2}d\rceil$ qubits, in which each qudit state $|a\rangle$ is encoded as the qubit computational basis state labeled by the binary representation of the integer a. The one-hot encoding uses more qubits but supports a simpler compilation of the single-qudit ring mixer for general d, both in the sense of it being much easier to write down a compilation, and in the sense that it uses many fewer two-qubit gates; in the one-hot encoding, 2-local mixing interactions suffice, whereas binary encoding requires $\lceil {log}_{2}d\rceil$-local Hamiltonian terms, with the corresponding unitary requiring further compilation to two-qubit gates.

In the one-hot encoding, the single-qudit ring mixer is encoded as a qubit unitary $U_{\mathrm{ring}}^{(\mathrm{enc})}$ corresponding to the qubit Hamiltonian: which acts on the qubit Hilbert space in a way that preserves the Hamming weight of computational basis states and acts as $U_{\mathrm{ring}}$ on the encoded subspace spanned by unit Hamming weight computational basis states.

Although $H_{\mathrm{ring}}^{(\mathrm{enc})}$ is 2-local, its terms do not mutually commute. There are several implementation options. First, hardware that natively implements the multiqubit gate $U_{\mathrm{ring}}^{(\mathrm{enc})}$ directly may be plausible (much as quantum annealers already support the simultaneous application of a Hamiltonian to a large set of qubits), but most proposals for universal quantum processors are based on two-qubit gates, so a compilation to such gates is desirable both for applicability to hardware likely to be available in the near term and for error-correction and fault tolerance in the longer term. Second, we could use constructions used in quantum many-body physics to compile $U_{\mathrm{ring}}^{(\mathrm{enc})}$ into a circuit of 2-local gates [38]. Third, the multiqubit gate $U_{\mathrm{ring}}^{(\mathrm{enc})}$ could be implemented approximately via Trotterization or other Hamiltonian simulation algorithms. A different approach, and the alternative we explore most extensively here, is to implement a different unitary rather than $U_{r-\mathrm{NV}}$, one related to $U_{r-\mathrm{NV}}$, and sharing its desirable mixing properties, as encapsulated in the design criteria of Section 3.1, which is easier to implement. The form of the circuit obtained by Trotterization is suggestive. We considered sequentially applying unitaries corresponding to subsets of terms in the Hamiltonian, each subset chosen in such a way that the corresponding unitary is readily implementable. This reasoning mirrors the relation of H-QAOA circuits to Trotterized AQO. We give a few examples of mixers obtained in this way.

Parity single-qudit ring mixer. Still in the one-hot encoding, we partitioned the d terms $e^{-i\beta \left(X_a{X}_{a+1}+Y_a{Y}_{a+1}\right)}$ by the parity of their indices. Let: where:

Such “XY” gates are natively implemented on certain superconducting processors [39].

It is easy to see that the parity single-qudit ring mixer preserves the Hamming weight and hence meets the first criterion of keeping the evolution within the feasible single-qudit subspace. To see that it also meets the second, providing transitions between all feasible computational basis states, it is useful to consider the quantum swap gate, which behaves in exactly the same way as the XY gate on the subspace spanned by $\left\{|0_i{1}_j\rangle ,|1_i{0}_j\rangle \right\}$. The swap gate ${\mathrm{SWAP}}_{i,j}=\frac{1}{2}(I+X_i{X}_j+Y_i{Y}_j+Z_i{Z}_j)$ is both unitary and Hermitian, and thus:

For $0<\beta <\pi /2$, each term in the parity single-qudit ring mixer is a superposition of a swap gate and the identity. A single application of $U_{\mathrm{parity}}(\beta )$ will have nonzero transition amplitudes only between pairs of colors with indices no more than two apart. Nevertheless, this mixer meets the second criteria because all possible orderings of d swap gates appear in $\lceil \frac{d}{2}\rceil$ repeats of the parity operator for any $0<\beta <\pi /2$, thus providing nonzero amplitude transitions between all feasible computational basis states for a single-vertex graph.

When d is an integer power of two, there is also a straightforward, though more resource-intensive, compilation of the parity single-qudit ring mixer using the binary encoding. Applying a Pauli X gate to the least-significant qubit acts as $H_{\mathrm{even}}$ on the encoded subspace. Incrementing the register by one, applying the Pauli gate to the least-significant qubit, and finally decrementing the register by one overall acts as $H_{\mathrm{odd}}$. Therefore, we can implement $U_{\mathrm{parity}}$ by incrementing the register by one, applying an $X(\beta )=e^{-i\beta X}$ to the least-significant qubit, decrementing the register by one, and then again applying an $X(\beta )$ gate to the least-significant qubit. For an l-bit register, each incrementing and decrementing operation can be written as a series of l multiply-controlled X gates, with the numbers of control ranging from 0 to $l-1$.

Repeated parity single-qudit ring mixers. As we mentioned above, a single application of $U_{\mathrm{parity}}(\beta )$ will have nonzero transition amplitudes only between pairs of colors with indices no more than two apart, which suggests that it may be useful to repeat the parity mixer within one mixing step.

Partition single-qudit ring mixers. We now generalize the above construction for the parity single-qudit ring mixer to more general partition mixers. For a given ordered partition $\mathcal{P}=(P_1,\dots ,P_p)$ of the terms of $H_{r-\mathrm{NV}}$ such that all pairs of terms within a $P_i$ act on disjoint states of the qudit, let: where:

By construction, in the one-hot encoding, the terms of $U_{P-\mathrm{XY}}$ commute (because they act on disjoint pairs of qubits), and so the ordering does not matter; all can be implemented in parallel. We call $U_{\mathcal{P}-r-\mathrm{NV}}$ the “partition $\mathcal{P}$” r-nearby-values single-qudit ring mixer, and $U_{r-\mathrm{NV}}$ the “simultaneous” r-nearby-values single-qudit ring mixer to distinguish the latter from the former. The latter is member of H-QAOA, while the former is not.

Even more generally, for a set of single-qudit ring mixers $\left\{H_{\alpha }\right\}$ indexed by some $\alpha$ and an ordered partition $\mathcal{P}=(P_1,\dots ,P_p)$ thereof, in which the single-qudit mixers within each part mutually commute, we defined a simultaneous version, $e^{-i\beta {\sum }_{\alpha }{H}_{\alpha }}$ and a $\mathcal{P}$-partitioned version, ${\prod }_{i=1}^P\left[{\prod }_{\alpha \in P_i}{e}^{-i\beta H_{\alpha }}\right]$, where the order of the product over the elements of each part does not matter because they commute, and the order of the product over the parts of the partition is given by their ordering within the ordered partition $\mathcal{P}$.

Binary single-qudit mixer for $d=2^l$. We now return briefly to the binary encoding, and describe a different single-qudit mixer. An alternative to the r-nearby values single-qudit mixer, which is easily implementable using the binary encoding when $d=2^l$ is a power of two, is the “simple binary” single-qudit mixer: where $X_i$ acts on the ith qubit in the binary encoding of the qudit. Since the ordering of the colors was arbitrary to begin with, it does not much matter whether the Hamiltonian mixes nearby values in the ordering or mixes the colors in a different way, in this case to colors with indices whose binary representations have Hamming distance 1.

When d is not a power of 2, a straightforward generalization of the binary single-qudit mixer experiences difficulty in meeting the first of the design criteria, since swapping one of the bit values in the binary representation may take the evolution out of the feasible subspace. While requiring d to be a power of 2 restricts its general applicability, the binary single-qudit mixer could be useful in some interesting cases, such as 4-coloring. For 2-coloring (a problem equivalent to MaxCut), the full binary single-qudit mixer is simply the standard mixer X. We use this encoding in Section 5.2 to handle slack variables in a single-machine scheduling problem, a case in which there is flexibility in the upper range of the integer to be encoded, allowing us to round up to the nearest power of two when needed.

Having introduced several partial mixers for single qudits, we now show a complete QAOA circuit for MaxColorableSubgraph with n vertices, m edges, and $\kappa$ colors, compiled to 2-local gates on qubits. Using the one-hot encoding, we require $n\kappa$ qubits.

Mixing operator. We used as the full mixer a parity ring mixer made up of parity single-qudit ring mixers, one for each of the qudits corresponding to each vertex:

The single qubit mixers act on different qubits and can be applied in parallel. The overall parity mixing operator required a depth-2 or depth-3 circuit (for even and odd $\kappa$, respectively) of $n\kappa$ gates. Other single-qudit mixers we defined above, including r repeats of the parity ring mixer, other partitioned mixers, or the binary mixer, could be used in place of the parity single-qudit mixer in this construction. All of these unitary mixers by construction meet our first criterion for a mixer: Keeping the evolution in the feasible subspace. Further, each of these mixers, after at most $\lceil \frac{\kappa }{2}\rceil$ repeats, provides nonzero amplitude transitions between all colors at a given vertex, with the product providing transitions between any two feasible states.

Phase-separation operator. The objective function can be written in classical one-hot encoding as: where $x_{v,a}=1$, indicating that vertex v has been assigned color a. To obtain a phase-separation Hamiltonian, we substituted $(I-Z)/2$ for each binary variable to obtain:

The constant term affects only a physically-irrelevant global phase, and since we are only concerned about the feasible subspace, we can disregard each sum ${\sum }_{a=1}^{\kappa }{Z}_{u,a}$ of all $\kappa$ single Z operators corresponding to a single qudit, since they multiply each of the d Hamming weight 1 elements corresponding to the d single qudit values by the same constant, resulting in a global phase. Removing those terms and rescaling, the phase separator now has the simpler form: where $Z_{v,a}$ acts on the ath qubit in the one-hot encoding of the vth qudit, corresponding to coloring vertex v with color a. The phase separator requires a circuit containing $m\kappa$ two-qubit gates with depth at most $D_G+1$, where $D_G$ is the maximum degree over all vertices in the instance graph G.

Translated back to acting on qudits, Equation (17) acts as $H_{\mathrm{P}}=H_g$ (as defined in Equation (3)), where $g(\mathbf{x})=\kappa m-4f(\mathbf{x})$. We refer to this function g as the “phase function”, which will typically be an affine transformation of the objective function, which corresponds simply to a physically irrelevant global phase and a rescaling of the parameter. Defining $H_{\mathrm{P}}$ using such a phase function allows us to write a simpler encoded version $H_{\mathrm{P}}^{(\mathrm{enc})}$ that corresponds exactly to $H_{\mathrm{P}}$, without qualification, on the encoded subspace.

Initial state. Any encoded coloring can be generated by a depth-1 circuit of at most n single-qubit X gates. A reasonable initial state is one in which all vertices are assigned the same color. Alternatively, we could start with any other feasible state, or the initial state could be obtained by applying one or more rounds of the mixer to a single feasible state, so that the algorithm begins with a superposition of feasible states.

The circuit depth and gate count for the full algorithm will increase when compiling to realistic near-term hardware with architectures that have nearest neighbor topological constraints limiting between which pairs of physical qubits two-qubit gates can be applied. See Reference [22] for one approach for compiling to realistic hardware with such constraints.

Further investigation is needed to understand which mixers and initial states, for a given resource budget, result in more or less effective algorithms, and whether some have an advantage with respect to finding good parameters ${\gamma }_1,\dots ,{\gamma }_p$, and ${\beta }_1,\dots ,{\beta }_p$ or being robust to error.

Given an independent set $V^{\prime }$, we can add a vertex $w\notin V^{\prime }$ to $V^{\prime }$ while maintaining feasibility only if none of its neighboring vertices $\mathrm{nbhd}(w)$ are already in $V^{\prime }$. On the other hand, we can always remove any vertex $w\in V^{\prime }$ without affecting feasibility. Hence, a bit-flip operation at a vertex, controlled by its neighbors (adjacent vertices), suffices both to remove and add vertices while maintaining the independence property. These classical moves inspire the controlled-bit-flip partial mixing operators.

In general, for a string $\mathbf{y}$ and a set of indices V, let ${\mathbf{y}}_V={\left(y_{v_i}\right)}_{i=1}^{\left|V\right|}$ be the substring of $\mathbf{y}$ in lexicographical order of the indices. In particular, let ${\mathbf{x}}_{\mathrm{nbhd}(v)}={\left(x_w\right)}_{w\in \mathrm{nbhd}(v)}$. (The ordering of the characters within the substring is arbitrary, because we only use this as the argument to predicates that are symmetric under permutation of the arguments.) For each vertex, we defined the partial mixer as a multiply-controlled X operator: with corresponding partial mixing unitary, a multiply-controlled-$X(\beta )$ single-qubit rotation: where $X_v(\beta )$ is the single-qubit operator $X_v(\beta )=e^{-i\beta X_v}$. Since $X_v$ is both Hermitian and unitary, $e^{-i\beta X_v}$ is a linear combination of the identity and $X_v$ for $0<\beta <\pi /2$.

Mixing operators. Let $H_{\mathrm{CX}}={\sum }_{i=1}^n{H}_{\mathrm{CX},v_i}$. We defined two distinct types of mixers:

where $\mathcal{P}$ is an ordered partition of the partial mixers, in which each part contains mutually commuting partial mixers. Since the partial mixers often do not commute, different ordered partitions often result in different mixers. By design, both the simultaneous and partitioned mixers restrict evolution to the feasible subspace. With respect to the second design criterion, there is nonzero transition amplitude from the ${|0\rangle }^{\otimes n}$ state corresponding to the empty set to all other independent sets; for $0<\beta <\pi /2$, we got terms corresponding to products of the individual control-bit-flip operators for all subsets of vertices, including those corresponding to independent sets. (For those subsets S not corresponding to independent sets, the product will result in a independent set $V^{\prime }\in S$ that does not include vertices in S which have neighbors whose controlled-bit-flip preceded them in the partition order; thus, different ordered partition affects the amount of nonzero amplitude in the states corresponding to independent sets.) Two applications of any such partitioned mixer result in nonzero amplitude between any two feasible states. An interesting question is how different ordered partitions affect the ease with which good parameters can be found and the quality of the solutions obtained.

Partitioned mixers are generally easier to compile than the simultaneous mixer, since the partitioned mixer is a product of multiqubit-controlled-not operators (generalized Toffoli gates) on at most $D_G+1$ qubits. Altogether, this construction uses n partial mixers, which can then be compiled into single- and two-qubit gates. For many graphs, partitions in which each set contains multiple commuting partial mixers exist, reducing the depth.

Phase-separation operator. The objective function is the size of the independent set, or $f(\mathbf{x})={\sum }_{i=1}^n{x}_i$, which we could translate into a phase-separating Hamiltonian via substitution of $(I-Z)/2$ for each binary variable. Instead, we used affine transformation of the objective function $g(\mathbf{x})=n-2f(\mathbf{x})$, which, when translated, yields a phase separation operator of a simpler form: which is simply a depth-1 circuit of n single-qubit Z-rotations.

Initial state. A reasonable initial state is the trivial state $|s\rangle ={|0\rangle }^{\otimes n}$ corresponding to the empty set.

The controlled null-swap partial mixer we defined has elements of the mixers we saw for the previous two problems, combining the control by vertex neighbors from MaxIndependentSet and the color swap from MaxColorableSubgraph. Here, however, we made substantial use of the uncolored state, and at each vertex only considered swapping a color with uncolored status. An uncolored vertex can be assigned color c, maintaining feasibility, as long as none of its neighbors are colored c, whereas uncoloring a vertex always preserves feasibility. This suggests a mixer may be obtained by swaps between each color and the uncolored state, controlled for each vertex by the colors of its neighboring vertices to ensure feasibility. This reasoning in terms of classical moves inspires, for problems containing $\mathsf{NEQ}$ constraints, the controlled null-swap partial mixing Hamiltonian: with corresponding controlled null-swap-rotation mixing unitary: where: is shorthand for none of the variables in $\mathbf{y}$ having value any of the values in A; when $A=\left\{a\right\}$ is a singleton set, we write simply $\mathsf{NONE}(\mathbf{y},a)=\mathsf{NONE}(\mathbf{y},\{a\})$.

Mixing operators. Define:

We defined two distinct types of mixers:

Again, we have a variety of partitioned mixers, each specified by an ordered partition $\mathcal{P}$ of the vertices such that for each color the terms corresponding to the vertices in the partition commute. We segregated the colors into separate stages, but other orderings are possible.

We used the one-hot encoding of Section 4.1, but with additional variables $x_{v,0}$ for the uncolored states: The binary variables for each vertex v are $x_{v,0},x_{v,1},\dots ,x_{v,k}$. This encoding uses $n(\kappa +1)$ computational qubits. In this encoding, a single partial mixer has the form: where ${\overline{\mathbf{x}}}_{\mathrm{nbhd}(v),a}={\left(x_{w,a}\right)}_{w\in \mathrm{nbhd}(v)}$. Reasoning similar to that we used for the mixers discussed for the MaxIndependentSet and MaxColorableSubgraph problems shows that this mixer has nonzero transition amplitude between any feasible computational-basis state and the trivial state corresponding to the empty set as the induced subgraph. Two applications of this mixer give nonzero transition amplitudes between any two feasible computational-basis states.

To ease compilation, each partial mixer can be implemented as: where the control is intermediated by an ancilla qubit, which is initialized and returns to the zero state. Altogether, this construction uses $\kappa n$ partial mixers, which can then be compiled into single- and two-qubit gates. For many graphs, partitions in which each set contains multiple commuting partial mixers exist, reducing the depth.

Phase-separation operator. We can translate the objective function to a Hamiltonian as usual, or translate a linear modification of the objective function to obtain a simpler form. The phase separator function $g(\mathbf{x})=n-2f(\mathbf{x})$ yields the simple phase separator Hamiltonian: for which the corresponding unitary operator can be implemented using a depth-1 circuit of n single-qubit Z-rotations.

Initial state. A reasonable initial state is $|s\rangle ={\left(|1\rangle \otimes {|0\rangle }^{\otimes \kappa }\right)}^{\otimes n}$, corresponding to all vertices uncolored.

We used a controlled version of the mixer in Section 4.1 that allows a vertex to change colors only when doing so would not result in an improper coloring; we may swap colors a and b at vertex v only if none of its neighbors are colored a or b. The partial mixer we defined has a similar form to the controlled null-swap partial mixer defined in Equations (27) and (28) but supports color changes between any two colors at a vertex, rather than only between colored and uncolored. Define the controlled-swap partial mixing Hamiltonian: with corresponding controled-swap-rotation mixing unitary: where $\mathsf{NONE}(\mathbf{x},A)$ was defined in Equation (29). These mixers are controlled versions of the single qudit fully-connected mixer of Section 4.1, rather than the single qudit ring mixer, which makes sure that every possible state is reachable.

Mixing Operator. Let:

We defined two types of mixers:

As before, each partitioned mixer is specified by an ordered partition $\mathcal{P}$ of the vertices such that, for each color, the partial mixers for vertices in one set of the partition all commute with each other. Altogether, this construction uses $(\kappa -1)\kappa n/2$ partial mixers, For many graphs, partitions in which each set contains multiple commuting partial mixers exist, allowing different partial mixers to be carried out in parallel, reducing the depth.

Phase-separation operator. The objective function, $f:{\left[\kappa \right]}^n\to {\mathit{Z}}_{+}$, is: which counts the numbers of colors used. Let $g(\mathbf{x})=\kappa -f(\mathbf{x})$ be the phase operator that counts the number of colors not used. Let $H_{\mathsf{NONE}(\mathbf{x},a)}$ be the projector onto the subspace of $\mathcal{H}$ spanned by the states corresponding to strings in ${\left[\kappa \right]}^n$ that do not contain the character a. We have $H_g={\sum }_a{H}_{\mathsf{NONE}(\mathbf{x},a)}$, so:

Initial state. For the initial state, we used an easily found $D_G+1$ (or $D_G+2$) coloring.

We now give partial compilations of the elements of the mapping to qubits using the one-hot encoding.

Mixer. In the one-hot encoding, the controlled-swap mixing Hamiltonian can be written as: with the corresponding unitary written as: where, for a string doubly indexed $\mathbf{y}={\left(y_{i,j}\right)}_{i,j}$, ${\mathbf{y}}_{A,B}={\left({\left(y_{i,j}\right)}_{i\in A}\right)}_{j\in B}$ denotes the substring consisting the characters $y_{i,j}$ for which $i\in A$ and $j\in B$, in lexicographical ordering of the two indices. In particular, ${\mathbf{x}}_{\mathrm{nbhd}(v),\{a,b\}}$ indicates the bits corresponding to coloring the neighbors of v either color a or color b. The ${\Lambda }_{\mathsf{NOR}(x_{\mathrm{nbhd}(v),\{a,b\}})}$ dictates that none of the neighbors of v take value a or b for the swap to be performed. Each $U_{\mathrm{CS},v,\{a,b\}}$ is a controlled gate with $2D_v$ control qubits and two target qubits. Altogether, the full mixing Hamiltonian can be implemented using $\kappa (\kappa -1)n/2$ controlled gates on no more than $D_G+2$ qubits.

Phase separator. Let $U_{\mathrm{P},a}(\gamma )=e^{-i\gamma H_{\mathsf{NONE}(\mathbf{x},a)}}$, so that the phase separator Equation (40) can be written as $U_{\mathrm{P}}(\gamma )={\prod }_{a=1}^{\kappa }a{U}_{\mathrm{P}}{U}_{\mathrm{P},a}(\gamma )$. Each partial phase separator can alternatively be written as:

Initial state. Any coloring can be prepared in depth 1 using n single-qubit X gates:

The configuration space here is the set of all orderings of the cities. Labeling the cities by $\left[n\right]$, the ordering $\mathit{\iota }=({\iota }_1,{\iota }_2,\dots ,{\iota }_{n-1},{\iota }_n)$ indicates traveling from city ${\iota }_1$ to city ${\iota }_2$, then on to city ${\iota }_3$ and so on until finally returning from city ${\iota }_n$ back to city ${\iota }_1$. The configuration space includes some degeneracy in solutions with respect to cyclic permutations; specifically, for any ordering $\mathit{\iota }$, the configuration space includes both $({\iota }_1,{\iota }_2,\dots ,{\iota }_{n-1},{\iota }_n)$ and $({\iota }_2,{\iota }_3,\dots ,{\iota }_n,{\iota }_1)$, 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: where we again and throughout employed the convention ${\iota }_{n+1}:={\iota }_1.$

Ordering swap partial mixing Hamiltonians. Our mixers for orderings will be built from partial mixer Hamiltonians we call “value-selective ordering swap mixing Hamiltonians.” Consider $\{{\iota }_i,{\iota }_j\}=\{u,v\}$, indicating that city u (resp. v) is visited at the ith (resp. jth) stop on the tour, or vice versa. There are ${\left(\genfrac{}{}{0pt}{}{n}{2}\right)}^2$ value-selective ordering swap mixing Hamiltonians, $H_{\mathrm{PS},\{i,j\},\{u,v\}}$, which swap the ith and jth elements in the ordering if and only if those elements are the cities u and v:

We made extensive use of a special case, the adjacent ordering swap mixing Hamiltonians:

To swap the ith and jth elements of the ordering regardless of which cities those are, we used the value-independent ordering swap partial mixing Hamiltonian:

Of these $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ partial mixing Hamiltonians, n are adjacent value-independent ordering swap partial mixing Hamiltonians: which swap the ith 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_{\mathrm{PS}}={\sum }_{i=1}^n{H}_{\mathrm{PS},i}$, we have the “simultaneous ordering swap mixer”:

Different subsets and partitions of the partial mixers $U_{\mathrm{PS},\{i,j\},\{u,v\}}=e^{-i{H}_{\mathrm{PS},\{i,j\},\{u,v\}}}$ and different orderings of a partition yield different partitioned ordering swap mixers. The color parity mixers we now defined use the adjacent partial mixer. Other mixers, using more of the ${\left(\genfrac{}{}{0pt}{}{n}{2}\right)}^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_{\mathrm{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_{\mathrm{PS},i,\{u,v\}}$ and $U_{\mathrm{PS},i,\{u^{\prime },v^{\prime }\}}$ commute as long as $\{u,v\}\cap \{u^{\prime },v^{\prime }\}=\varnothing$. Partitioning the $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ 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}}_{\mathrm{col}}=(P_1,\dots ,P_c,\dots ,P_{\kappa })$ 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}}_{\mathrm{col}}=\left(\left\{\{1,2\},\{3,4\}\right\},\left\{\{1,3\},\{2,4\}\right\},\left\{\{1,4\},\{2,3\}\right\}\right)$. For different tour positions i, two partial unitaries $U_{\mathrm{PS},i,\{u,v\}}$ and $U_{\mathrm{PS},i^{\prime },\{u^{\prime },v^{\prime }\}}$ commute if i and $i^{\prime }$ are not consecutive ($|i-i^{\prime }modn|>1$). Thus, for partitioning the positions, we may use the parity partition ${\mathcal{P}}_{\mathrm{par}}$, as defined in Section 4.1. We can thus define the “color-parity” ordered partition ${\mathcal{P}}_{\mathrm{CP}}={\mathcal{P}}_{\mathrm{col}}\times {\mathcal{P}}_{\mathrm{par}}$, with the induced lexicographical ordering of the parts. The part $P_{c,\mathrm{odd}}$ contains all $U_{\mathrm{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: where the ordering of the products does not matter because each term commutes. It is a similar case for $P_{c,\mathrm{even}}$ and $U_{c,\mathrm{even}}$, and $P_{c,\mathrm{last}}$ and $U_{c,\mathrm{last}}$. Thus, we have the full color-parity mixer: where the unitaries $\left\{U_{c,\pi }\right\}$ are applied in the order they appear in ${\mathcal{P}}_{\mathrm{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$.

Encoding orderings. We encoded orderings in two stages: First into strings, and then into bits making use of the encodings from Section 4. Here, we focus on a “direct encoding” as opposed to the “absolute encoding” that is introduced in Section 5.3. Other encodings of orderings are possible, such as the Lehmer code and inversion tables. In direct encoding, an ordering $\mathit{\iota }=\left({\iota }_1,\dots ,{\iota }_n\right)$ is encoded directly as a string ${\left[n\right]}^n$ of integers. Once in the form of strings, any of the string encodings introduced in Section 4 can be applied. We applied the one-hot encoding with $n^2$ binary variables; the binary variable $x_{j,u}$ indicates whether or not ${\iota }_j=u$ in the ordering, in other words, whether city u is visited at the j-th stop of the tour.

Phase separator. We used the phase function $g(\mathit{\iota })=4f(\mathit{\iota })-(n-2){\sum }_{u=1}^n{\sum }_{v=1}^{n}d(u,v)$, which translates to a phase separator encoded as: The phase separating unitary corresponding to Equation (53) imparts a phase determined by the sum of the distances between successive cities to a state corresponding to a tour. This unitary can be implemented using $n^2(n-1)$ two-qubit gates, which mutually commute. Using the same color-parity partition of the terms as for the color-parity ordering swap mixer, this can be done in depth $2\kappa \le 2n$.

Mixer. The individual value-selective ordering swap partial mixer, which swaps cities u, v between tour positions i and j, is expressed in the one-hot encoding as: where: