# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 2 Background
### The Original Quantum Approximate Optimization Algorithm  
We now give an overview of the original quantum approximation optimization algorithm proposed in Reference [PERSON] et al. (2016).  
Consider an unconstrained optimization problem on \(n\)-bit strings we seek to approximate. Given a problem instance, the algorithm is specified by two Hamiltonians \(H_{\text{P}}\) and \(H_{\text{M}}\), and \(2p\) real parameters \(\gamma_{1},\ldots,\gamma_{p},\beta_{1},\ldots,\beta_{p}\). The main details are the following:  
* The _phase Hamiltonian_\(H_{\text{P}}\) encodes the cost function \(f\) to be optimized, i.e., acts diagonally on \(n\)-qubit computational basis states as: \[H_{\text{P}}\ket{\mathbf{y}}=f(\mathbf{y})\ket{\mathbf{y}}.\]
* The _mixing Hamiltonian_\(H_{\text{M}}\) is the transverse field Hamiltonian: \[H_{\text{M}}=\sum_{j=1}^{n}X_{j},\] where \(X_{j}\) is the Pauli \(X\) operator acting on the \(j\)th qubit. (The Pauli \(X\) operator acts as a bit flip, i.e., \(X\ket{0}=\ket{1}\) and \(X\ket{1}=\ket{0}\).)
* The initial state is selected to be the equal superposition state of all possible solutions: \[\ket{s}=\frac{1}{\sqrt{2^{n}}}\sum_{x}\ket{x}\,\]which is also the ground-state of \(-H_{M}\) and is used similarly in AQO [1].
* A _parameterized quantum state_ is created by alternately applying Hamiltonians \(H_{\text{P}}\) and \(H_{\text{M}}\) for \(p\) rounds, where the duration in round \(j\) is specified by the parameters \(\gamma_{j}\) and \(\beta_{j}\), respectively: \[\left|\beta,\gamma\right\rangle=e^{-i\beta_{p}H_{\text{M}}}e^{-i\gamma_{p}H_{ \text{P}}}\cdots e^{-i\beta_{2}H_{\text{M}}}e^{-i\gamma_{2}H_{\text{P}}}e^{-i \beta_{1}H_{\text{M}}}e^{-i\gamma_{1}H_{\text{P}}}\left|s\right\rangle.\]
* A computational basis measurement is performed on the state, which returns a candidate solution \(\mathbf{y}\) with probability \(|\left.\left\langle\mathbf{y}\right|\right.\left|\beta,\gamma\right\rangle \right|^{2}\). Repeating the above state preparation and measurement, the expected value of the cost function over the returned solution samples is given by: \[\left\langle f\right\rangle=\left\langle\beta,\gamma\right|H_{\text{P}}\left| \beta,\gamma\right\rangle,\] which can be statistically estimated from the samples produced. (For a constraint satisfaction problem with \(m\) constraints, fom Chebyshev's inequality it follows that an outcome achieving at least \(\left\langle f\right\rangle-1\) will be obtained with probability at least \(1-1/m\) after \(O(m^{2})\) repetitions.)
* The above steps may then be repeated altogether, with updated sets of time parameters, as part of a classical optimization loop (such as gradient descent or other approaches) used to optimize the algorithm parameters with respect to an objective such as \(\left\langle f\right\rangle\).
* The best problem solution found overall is returned.  
A key to success for the algorithm is the selection or discovery of good values for the parameters \(\gamma_{1},\ldots,\gamma_{p},\beta_{1},\ldots,\beta_{p}\), which result in good approximate solutions. In some cases, where the analysis is tractable, such angles may be found analytically [19; 21]. Parameter setting strategies for QAOA and for the general class of variational quantum algorithms remains an active area of research [33; 34].  
We now turn to our generalized QAOA framework, which is the main subject of the paper.