# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 2 Background  
Over the last few decades, researchers have discovered several stunning instances of quantum algorithms that provably outperform the best existing classical algorithms and, in some cases, the best possible classical algorithm [8]. For most problems, however, it is currently unknown whether quantum computing can provide an advantage, and if so, how to design quantum algorithms that realize such advantages. Today, challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms, which by definition have not been analytically proven to be the best approach, or even proven analytically to outperform the best approach of the previous year. For several years now, special-purpose quantum hardware has been used to explore one quantum heuristic algorithm, quantum annealing. Emerging gate-model processors will enable investigation of a much broader array of quantum heuristics beyond quantum annealing. Within the last year, IBM has made available publicly through the cloud a gate-model chip with 5 and 16 superconducting qubits [9], and it recently announced an upgrade to a 20-qubit chip. Likewise, Google [10] and Rigetti Computing [11] anticipate to provide processors with 40-100 superconducting qubits within a year [12]. Many academic groups, including at TU Delft and at UC Berkeley, have made similar efforts. In addition to superconducting architectures, ion [13] and neutral atom based [14] devices are also reaching the scale at which intermediate-size experiments would be feasible [12]. Gate-model quantum computing expands the empirical evaluation of quantum heuristics applications beyond optimization of classical functions, as well as enabling a broader array of approaches to optimization [15]. While limited exploration of quantum heuristics beyond quantum annealing has been possible through small-scale classical simulation, the exponential overhead in such simulations has limited their usefulness. The next decade will see a blossoming of quantum heuristics as a broader and more flexible array of quantum computational hardware becomes available. The immediate question is: What experiments should we prioritize that will give us insight into quantum heuristics? One leading candidate is the quantum approximate optimization algorithm (QAOA), for which a number of tantalizing related results have been obtained [16; 17; 18; 19; 20; 21; 22] since [PERSON] et al. 's initial paper [1]. In QAOA, a phase-separation operator, usually the problem Hamiltonian that encodes the cost function of the optimization problem, and a mixing Hamiltonian are applied in alternation. The class QAOA\({}_{p}\) consists of level-\(p\) QAOA circuits, in which there are \(p\) iterations of applying a classical Hamiltonian (derived from the cost function) and a mixing Hamiltonian. The \(2p\) parameters of the algorithm specify the durations for which each of these two Hamiltonians are applied. Prior work suggests the power and flexibility of QAOA circuits. [PERSON] et al. [PERSON] et al. (2016) exhibited a QAOA\({}_{1}\) algorithm that beat the existing best approximation bound for efficient classical algorithms for the problem E3 Lin2, only to inspire a better classical algorithm [PERSON] et al. (2019). [PERSON] et al. (2019) demonstrated that the class of QAOA circuits is powerful enough to obtain the \(\Theta(\sqrt{2^{n}})\) query complexity on [PERSON]'s problem and also provided the first algorithm within the QAOA framework to show a quantum advantage for a finite number of iterations greater than two. [PERSON] and [PERSON] [PERSON] and [PERSON] (2017) proved that, under reasonable complexity assumptions, the output distribution of even QAOA\({}_{1}\) circuits cannot be efficiently sampled classically. [PERSON] et al.