Southwest Quantum Information and Technology

A hybrid quantum approximate optimization algorithm incorporating classical heuristics

Presenting Author: Jaimie S. Stephens, Sandia National Laboratories
Contributing Author(s): William Bolden; Ojas Parekh

The Quantum Approximate Optimization Algorithm (QAOA) (Farhi et. al. 2014) can approximately solve NP-hard problems. However, the performance of QAOA is not well understood, especially relative to problem-specific classical heuristics. We propose boosting the performance of QAOA by leveraging classical heuristics as black-box oracles in a generic and automatic way. This allows QAOA to benefit from improved classical algorithms as they are discovered. We replace the QAOA cost Hamiltonian with an implicit cost operator derived from a classical heuristic of choice, allowing QAOA to optimize over the output of a classical heuristic. Our approach also eliminates the need for specially designed mixing Hamiltonians for constrained problems. We demonstrate our hybrid QAOA on several discrete optimization problems using high-quality classical heuristics, including local search. We observe that: (i) the performance of our hybrid QAOA improves as the computational cost of local-search is increased, and (ii) our hybrid QAOA outperforms both QAOA and the selected classical heuristics on their own. Thus we offer a new means for QAOA to automatically benefit from classical advances. 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, National Nuclear Security Administration under contract DE-NA0003525.

(Session 9a : Sunday from 5:15pm - 5:45pm)