Elementary proof of QAOA convergence

New Journal of Physics, vol. 26, pp. 073001

Abstract

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.

Authors 4

1. Lennart Binkowski

   Leibniz University Hannover

   Affiliation as printed

   Institute for Theoretical Physics, Leibniz Universität Hannover, Appelstraße 2, Hannover, 30167, GERMANY

2. Gereon Koßmann Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Nordrhein-Westfalen, GERMANY

3. Timo Ziegler

   Leibniz University Hannover

   Affiliation as printed

   Theoretische Physik, Leibniz Universität Hannover, Hannover, GERMANY

4. René Schwonnek corresponding

   Leibniz University Hannover

   Affiliation as printed

   Theoretische Physik, Leibniz Universität Hannover, Hannover, 30167, GERMANY