# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 6 Conclusions  
We introduced a quantum alternating operator ansatz (QAOA), an extension of [PERSON] et al. 's quantum approximate optimization algorithm, and showed how to apply the ansatz to a diverse set of optimization problems with hard constraints. The essence of this extension is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution of a local Hamiltonian, which allows it to represent a larger, and potentially more useful, set of states than the original formulation. In particular, refocusing on unitaries rather than Hamiltonians in the specification allows for more efficiently implementable mixing operators. The original algorithm is already a leading candidate quantum heuristic for exploration on near-term hardware; our extension makes early testing on emerging gate-model quantum processors possible for a wider array of problems at an earlier stage. After formally introducing the ansatz, and providing design criteria for its components, we worked through a number of examples in detail, illustrating design techniques and exhibiting a variety of mixing operators. In the appendix, we provide a compendium of QAOA mappings for over 20 problems, organized by type of mixer. While the approach of designing mixing operators to keep the evolution within the feasible subspace appears quite general, as illustrated by the wide variety of examples we have worked out, it is not universally applicable. Many of the problems in [PERSON] (1964) have the form of optimizing a quantity within a feasible subspace consisting of the solutions to an NP-complete problem. Not only is an initial starting state (corresponding to one or more feasible solutions) hard to find, designing the mixing operator is also problematic. Even given a set of feasible solutions to an NP-complete problem, it is typically computationally difficult to find another ([PERSON], 1964), making it difficult to design a mixer that fully explores the feasible subspace. The situation here is somewhat subtle, with it being easy to show in the case of SAT that finding a second solution when given a first remains NP-complete, but for a Hamiltonian cycle on cubic graphs, given a first solution, a second is easy to find (but not a third). See References (K  
and the feasibility of classically simulating the measurement of \(\log(n)\)-qubits in a QAOA circuit by adapting results for IQP circuits [45]. To run on near-term quantum hardware, further compilation will be required. In many cases, we have left the compilation at the level of multiqubit operators that need to be further compiled to the gate set natively available on the hardware, most likely certain one- and two-qubit gates. Clearly, issues such as connectivity will be critical to the implementability and success of QAOA circuits. Furthermore, near-term hardware will have additional restrictions, including which qubits each gate can be applied to, the duration and fidelity of the gates, and cross-talk, among others. This necessitates additional compilation, especially to optimize success probability on pre-fault-tolerant devices. Other architectures, e.g., ones based on higher-dimensional qudits, may prompt other sorts of compilations as well. Recently, approaches for compiling quantum circuits, including QAOA circuits, to realistic hardware have been explored [22; 35; 46], but that research direction remains open to innovation. An interesting research direction is to explore the power of quantum alternating operator ansatz states built from natively available gates and directly incorporating the connectivity of the underlying hardware. The robustness of these circuits to realistic error requires further exploration. In the near term, the question is how robust QAOA circuits are to realistic noise and how best to incorporate resource-efficient techniques to improve the robustness. In the longer term, the question becomes how to best incorporate the full spectrum of error correction techniques into this framework.