Elementary Proof of QAOA Convergence

Abstract

The Quantum Alternating Operator Ansatz (QAOA) and its predecessor, the Quantum Approximate Optimization Algorithm, are one of the most widely used quantum algorithms for solving combinatorial optimization problems. However, as there is yet no rigorous proof of convergence for the QAOA, we provide one in this paper. The proof involves retracing the connection between the Quantum Adiabatic Algorithm and the QAOA, and naturally suggests a refined definition of the `phase separator' and `mixer' keywords.

10 pages, 2 figures

References in corpus (3)

• A Quantum Approximate Optimization Algorithm
• Mathematical Foundation of Quantum Annealing
• Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study

Cited by in corpus (6)

• A quantum algorithm for solving 0-1 Knapsack problems
• Noise-aware variational eigensolvers: a dissipative route for lattice gauge theories
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem