Southwest Quantum Information and Technology

Quantum Approximate Optimization Algorithm (QAOA) on constrained optimization problems

Presenting Author: Jaimie S. Stephens, University of New Mexico CQuIC
Contributing Author(s): Ciarán Ryan-Anderson: Department of Physics, College of Science, Swansea University, Singleton Park, Swansea - SA2 8PP, United Kingdom; William Bolden: Center for Computing Research, Sandia National Laboratories, Albuquerque, NM, 87185, USA; Department of Computer Science and Engineering, University of California Santa Cruz, Santa Cruz, CA 95064, USA; Ojas Parekh: Center for Computing Research, Sandia National Laboratories, Albuquerque, NM, 87185, USA

While it is not widely believed that quantum computers will solve NP-Hard problems, they may be able to approximate the solution of such problems faster or with a better approximation than a classical computer can. In 2014, Farhi et.al. proposed the Quantum Approximate Optimization Algorithm, QAOA, to approximate hard optimization problems on a quantum computer. QAOA is naturally constructed to approximate unconstrained optimization problems but was not originally designed to account for constraints. In 2017, Hadfield et. al. proposed an adjustment to QAOA (QAOA++), so that it may be applied to constrained optimization problems. We compare this to Hen and Spedalieri's (2016) proposed method for Constrained Quantum Annealing (CQA). We show that these two methods for choosing a driving (mixing in Hadfield et. al.) Hamiltonian yield equivalent Hamiltonians for a given problem. This allows one to directly compare how QAOA++ and CQA perform on a given problem. In addition to these existing methods, we propose a new way of using QAOA to solve constrained optimization problems by adding a penalty Hamiltonian to the problem Hamiltonian, QAOA with penalties. Sandia National Labs is managed and operated by National Technology and Engineering Solutions of Sandia, LLC, a subsidiary of Honeywell International, Inc., for the U.S. DOE’s National Nuclear Security Administration under contract DE-NA0003525.

(Session 5 : Sunday from 5:00pm - 7:00pm)