From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

By Stuart Hadfield, Zhihui Wang, B. O’Gorman, E. Rieffel, Davide Venturelli, R. Biswas. Algorithms, 2017

938 citations recorded by the source corpus.

The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.’s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. 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. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/096022648d3ee2fa5f62e9ccf36fde9997f00893

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Challenges and opportunities in quantum optimization (2023, positive): “The quantum alternating operator ansatz 79,80 generalizes the QAOA to much wider classes of problems and encodings, in particular to problems with hard constraints.”
Connecting ansatz expressibility to gradient magnitudes and barren plateaus (2021, background): “For instance, the quantum alternating operator ansatz [21] (or the Hamiltonian variational ansatz [25]), encode information of an appropriate adiabatic transformation.”
Variational quantum algorithms (2020, methodology): “As discussed in Section II B, the UCC ansatz for VQE of the quantum alternating operator ansatz [22, 23] for optimization are problem-inspired ansatze which are usually trainable even when randomly initialized.”
QAOA for Max-Cut requires hundreds of qubits for quantum speed-up (2018, methodology): “Following an existing trend in the community [7, 13, 14, 16], we consider random 3-regular graphs, defined as having exactly 3 edges per vertex.”
Diagnosing Barren Plateaus with Tools from Quantum Optimal Control (2021, methodology): “Then the QAOA is given by U(θ) = ∏L l=1 e −iβlHM e−iγlHP , which follows the general form of the ansatz defined in (2).”
Variational Quantum Linear Solver (2019, methodology): “In addition to the aforementioned ansatz, one can also employ the Quantum Alternating Operator Ansatz (QAOA) [48, 49] to construct the unitary V ( α ) and avoid trainability issues.”
Unsupervised Machine Learning on a Hybrid Quantum Computer (2017, methodology): “However, QAOA does not specify how the optimal set of angles are found, although in some cases they can be derived analytically for a small number of iterations and for uniformly weighted graphs [11, 31].”