# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 3 The Quantum Alternating Operator Ansatz (QAOA)
### Design Criteria  
Here, we briefly specify design criteria for the three components of a QAOA mapping of a problem. We expect that as exploration of QAOA proceeds, these design criteria will be strengthened and will depend on the context in which the ansatz is used. For example, when the aim is a polynomial-time quantum circuit, the components should have more stringent bounds on their complexity; without such bounds, the ansatz is not useful as a model for a strict subset of states producible via polynomially-sized quantum circuits. On the other hand, when the computation is expected to grow exponentially, a simple polynomial bound on the depth of these operators might be reasonable. One example might be for exact optimization of the problems considered here; for these problems, the worst case algorithmic complexity is exponential, but it is worth exploring whether QAOA might outperform classical heuristics in expanding the tractable range for some problems. Initial state. We require that the initial state \(\ket{s}\) be _trivial_ to implement, by which we mean that it can be created by a constant-depth (in the size of the problem) quantum circuit from the \(\ket{0\ldots 0}\) state. Here, we often take as our initial state a single feasible solution, usually implementable by a depth-\(1\) circuit consisting of single-qubit bit-flip operations \(X\). Because in such a case the initial phase operator only applies a global phase, we may want to consider the algorithm as starting with a single-mixing operator \(U_{\text{M}}(\beta_{0})\) to the initial state as a first step. In the quantum approximate optimization algorithm, the standard starting state \(\ket{+\cdots+}\) is obtained by a depth-\(1\) circuit that applies a Hadamard \(H\) gate to each of the qubits in the \(\ket{0\ldots 0}\) state. This criterion could be relaxed to logarithmic depth if needed. It should not be relaxed too much: Relaxing the criterion to polynomial depth would obviate the usefulness of the ansatz as a model for a strict subset of states producible via polynomially-sized quantum circuits. Algorithms with more complex initial states should be considered hybrid algorithms, with an initialization part and a QAOA part. Such algorithms are of interest in cases when one expects the computation to grow exponentially, such as is the case for exact optimization for many of the problems here, but might still outperform classical heuristics in expanding the tractable range. Phase-separation unitaries. We require the family of phase-separation operators to be diagonal in the computational basis. In almost all cases, we take \(U_{\text{P}}(\gamma)=e^{-i\gamma H_{j}}\), where \(f\) is the objective function. Mixing unitaries (or \"mixers\"). We require the family of mixing operators \(U_{\text{M}}(\beta)\) to:  
* Preserve the feasible subspace: For all values of the parameter \(\beta\), the resulting unitary takes feasible states to feasible states, and;
* Provide transitions between all pairs of states corresponding to feasible points. More concretely, for any pair of feasible computational-basis states \(\mathbf{x},\mathbf{y}\in F\), there is some parameter value \(\beta^{*}\) and some positive integer \(r\) such that the corresponding mixer connects those two states: \(\left|\left\langle\mathbf{x}\,\right|\,U_{\text{M}}^{*}(\beta^{*})\,\middle| \,\mathbf{y}\right\rangle\right|>0\). In some cases, we may want to relax some of these criteria. For example, if a QAOA circuit is being used as a subroutine within a hybrid quantum-classical algorithm, or in a broader quantum algorithm, we may use starting states informed by previous runs and thus allow mixing operators that mix less. This framework can be used in many different contexts. Depending on the context, different measures of success are appropriate. As indicated by the name, the original motivation for [PERSON] et al. 's work was to develop a quantum approximation algorithm, one for which rigorous bounds on the approximation ratio can be proven [1; 16].