# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 3 The Quantum Alternating Operator Ansatz (QAOA)
The one exception is Section VIII of Reference [1], which discusses a variant for the maximum independent set problem, in which \(F\) is the set of bitstrings corresponding to the independent sets of a graph, the phase separator  
Figure 1: The quantum alternating operator ansatz (QAOA\({}_{p}\)) quantum circuit schematic. Here, an encoding to qubits for a given problem domain is assumed. The box shows an example decomposition of a QAOA mixing operator family \(U_{M}(\beta)\) into a sequence of partial mixers \(U_{M,\pm}(\beta)\). In this ansatz, a one-parameter family of mixing operators does not in general correspond to time evolution under a fixed mixing Hamiltonian \(H_{M}\). The construction of this paper includes different orderings of the partial mixers, resulting in a variety of inequivalent mixing operators with different implementation costs. Though not shown in the figure, phase and mixing operators will often include ancilla qubits to facilitate computation and simple compilation to one- and two-qubit gates. The circuit shown indicates measurement at the end of the algorithm; in general, a quantum alternating operator ansatz circuit may be instead embedded as part of a larger quantum algorithm. Likewise, different initial states may be used which may be constructed by design or the output of another quantum subroutine. depends on the cost function as above, and the mixing operator is \(U_{\text{M}}(\beta)=e^{-i\beta H_{B}}\), where \(H_{B}\) is such that:  
\[\langle\mathbf{x}|H_{B}|\mathbf{y}\rangle= \begin{cases}1,&\mathbf{x},\mathbf{y} \in F\text{ and }\text{Ham}(\mathbf{x},\mathbf{y})=1,\\ 0,&\text{otherwise},\end{cases}  \tag{4}\]  
which connects feasible qubit computational basis states with unit Hamming distance \((\text{Ham})\). Section VIII of Reference [1] does not discuss the implementability of \(U_{\text{M}}(\beta)\). A closely related generalization of QAOA for problems with hard constraints based on quantum walks has recently been proposed [31]. However, row-computable feasibility oracles are required to enable mixing between feasible states, which are likely to be more expensive to implement in practice than the approach of this paper. We extended and formalized the approach of Section VIII of Reference [1] with an eye to implementability, both in the short and long term. We also built on a theory developed for adiabatic quantum optimization (AQO) by [PERSON] and [PERSON] [6] and [PERSON] and [PERSON] [7], though the gate-model setting of QAOA leads to different implementation considerations than those for AQO. For example, [PERSON] et al. identified driver Hamiltonians of the form \(H_{\text{M}}=\sum_{j,k}H_{j,k}\), where \(H_{j,k}=X_{j}X_{k}+Y_{j}Y_{k}\), as useful in the AQO setting for a variety of optimization problems with hard and soft constraints; such mixers restrict the mixing to the feasible subspace defined by the hard constraints. Analogously, the unitary \(U_{\text{M}}=e^{-i\beta H_{\text{M}}}\) meets our criteria, discussed in Section 3.1, for good mixing for a variety of optimization problems, including those considered in References [6; 7]. Since \(H_{j,k}\) and \(H_{i,l}\) do not commute when \(|\{j,k\}\cap\{i,l\}|=1\), compiling \(U_{\text{M}}\) to two-qubit gates is nontrivial. One could Trotterize, but it may be more efficient and just as effective to use an alternative mixing operator, such as \(U_{\text{M}}=e^{-i\beta H_{S_{l}}}\cdots e^{-i\beta H_{S_{2}}}e^{-i\beta H_{S_{ 1}}}\), where the pairs of qubits have been partitioned into \(r\) subsets \(\{S_{i}\}_{i}\) containing only disjoint pairs, motivating in part our more general ansatz. We define as \"Hamiltonian-based QAOA\" (H-QAOA) the class of QAOA circuits in which both the phase separator family \(U_{\text{P}}(\gamma)=e^{-i\gamma H_{\text{P}}}\) and the mixing operator family \(U_{\text{M}}(\beta)=e^{-i\beta H_{\text{M}}}\) correspond to time evolution under some Hamiltonians \(H_{\text{P}}\) and \(H_{\text{M}}\), respectively.