# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 3 The Quantum Alternating Operator Ansatz (QAOA)  
Here, we formally describe the quantum alternating operator ansatz, extending the approach of [PERSON] et al. [1]. QAOA, in our sense, encompasses a more general class of quantum states that may be algorithmically accessible and useful. We focus here on the application of QAOA to approximate optimization, though it may also be used in exact optimization [19; 20] and sampling [17]. An instance of an _optimization problem_ is a pair \((F,f)\), where \(F\) is the _domain_ (set of feasible points) and \(f:F\rightarrow\mathbb{R}\) is the _objective function_ to be optimized (minimized or maximized). Let \(\mathcal{F}\) be the Hilbert space of dimension \(\left|F\right|\), whose standard basis we take to be \(\{\left|\mathbf{x}\right\rangle:\mathbf{x}\in F\}\). Generalizing Reference [1], a QAOA circuit is characterized by two parameterized families of operators on \(\mathcal{F}\):  
* A family of _phase-separation operators_\(U_{\text{P}}(\gamma)\) that depends on the _objective function_\(f\), and;
* A family of _mixing operators_\(U_{\text{M}}(\beta)\) that depends on the domain and its structure,  
where \(\beta\) and \(\gamma\) are real parameters. Specifically, a QAOA\({}_{p}\) circuit consists of \(p\) alternating applications of operators from these two families:  
\[Q_{p}(\beta,\gamma)=U_{\text{M}}(\beta_{p})U_{\text{P}}(\gamma_{p})\cdots U_{ \text{M}}(\beta_{1})U_{\text{P}}(\gamma_{1}). \tag{1}\]  
This quantum alternating operator ansatz (QAOA) consists of the states representable as the application of such a circuit to a suitably simple initial state \(\left|s\right\rangle\):  
\[\left|\beta,\gamma\right\rangle=Q_{p}(\beta,\gamma)\left|s\right\rangle. \tag{2}\]  
We show an overall quantum circuit schematic for a QAOA mapping in Figure 1 below. For a given optimization problem, a _QAOA mapping_ of a problem consists of a family of phase-separation operators, a family of mixing operators, and a starting state. The circuits for the original quantum approximate optimization algorithm fit within this paradigm, with unitaries of the form \(e^{-i\gamma H_{\mathrm{P}}}\) and \(e^{-i\beta H_{\mathrm{M}}}\), with parameters \(\gamma\) and \(\beta\) indicating the time for which a fixed Hamiltonian is applied. The domain will usually be expressed as the feasible subset of a larger _configuration space_, specified by a set of problem _constraints_. For implementation on expected near-term quantum hardware, each configuration space will need to be _encoded_ into a subspace of a Hilbert space of a multiqubit system, with the domain corresponding to a _feasible subspace_ of the configuration space. For each domain, there are many possible mixing operators. As we will see, using more general one-parameter families of unitaries enables more efficiently implementable mixers that preserve the feasible subspace. Given a domain, an encoding of its configuration space, a phase separator, and a mixer, there are a variety of _compilations_ of the phase separator and mixer to circuits that act on qubits. For any function \(f\), not just an objective (cost) function, we define \(H_{f}\) to be the quantum Hamiltonian that acts as \(f\) on basis states as:  
\[H_{f}\ket{\mathbf{x}}=f(\mathbf{x})\ket{\mathbf{x}}. \tag{3}\]  
In prior work, the domain \(F\) was the set of all \(n\)-bit strings, \(U_{\mathrm{P}}(\gamma)=e^{-i\gamma H_{f}}\), and \(U_{\mathrm{M}}(\beta)=e^{-i\beta H_{B}}\). Furthermore, with just one exception, the mixing Hamiltonian was \(H_{B}=\sum_{j=1}^{n}X_{j}\). We used the notation \(X_{j}\), \(Y_{j}\), \(Z_{j}\) to indicate the Pauli matrices \(X\), \(Y\), and \(Z\) acting on the \(j\)th qubit. The corresponding parameterized unitaries are denoted by \(X_{j}(\theta)=e^{-i\beta X_{j}}\) and similarly for \(Y_{j}\) and \(Z_{j}\).