# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 1 Introduction  
Today, challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms. These algorithms are empirically shown to be effective, but they have not beenanalytically proven to be the best approach, or even to outperform the best approach of the previous year. Until recently, empirical investigation of quantum algorithms has been limited to tiny problems, given the typically exponential overhead of simulating quantum algorithms on classical processors. As prototype quantum hardware emerges which enables experimentation beyond what is reachable by even the world's largest supercomputers, we come into a new era for quantum heuristic algorithms. A key question is: \"What are good quantum heuristic algorithms to try?\" A leading candidate is [PERSON] et al. 's quantum approximate optimization algorithm, a quantum gate-model meta-heuristic which alternates between applying unitaries drawn from two families, a cost function based unitary family \(U_{\text{P}}(\gamma)=e^{-i\gamma H_{f}}\) and a family of mixing unitaries \(U_{\text{M}}(\beta)=e^{-i\beta H_{B}}\), for some fixed cost function based Hamiltonian \(H_{f}\) and some fixed mixing Hamiltonian \(H_{B}\). Here, we formally describe a _quantum alternating operator ansatz_ (QAOA), extending the approach of [PERSON] et al. [1] to allow alternation between more general families of operators. This ansatz supports the representation of a much more varied, and potentially more useful, set of states than the original formulation. Our extension is particularly useful for situations in which the feasible subspace is smaller than the full space, such as when the optimization is over solutions that must satisfy hard constraints. Intuitively, mixing operators that restrict the search to the feasible subspace should result in better-performing algorithms. Our expansion includes families of mixing operators \(U_{\text{M}}(\beta)\) that cannot be expressed, as a family, as \(e^{-i\beta H_{B}}\) for a fixed mixing Hamiltonian \(H_{B}\). As we shall see, expanding the design space of families of one-parameter mixing operators allowed enables the ansatz to support more efficiently implementable mixers than was possible in the original framework. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. We carefully construct a framework for this ansatz, laying out design criteria for families of mixing operators. We detail QAOA mappings of several optimization problems, and provide a compendium of mappings for a diverse array of problems. These mapping range from the relatively simple, which could be implemented on near-term devices, to complex mappings with significant resource requirements. This paper is meant as a starting point for a research program. Improved mappings and compilations, especially for some of the more complex problems, are a promising area for future work. Architectural codesign could be used to enable experimentation of QAOA approaches to some problems earlier than would be possible otherwise. We reworked the original acronym so that \"QAOA\" continues to apply to both prior work and future work to be done in this more general framework. More generally, the reworked acronym refers to a set of states representable in a certain form, and so can be used without confusion in contexts other than approximate optimization, e.g., exact optimization and sampling. (Incidentally, this reworking also removes the redundancy from the now commonly-used phrase \"QAOA algorithm\"). After describing the framework for the ansatz, we show explicit mappings to quantum circuits and resource estimates for a diverse set of problems, designing phase separation and mixing operators appropriate for each problem.