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)


SQuInT Chief Organizer
Akimasa Miyake, Associate Professor

SQuInT Co-Organizer
Brian Smith, Associate Professor UO

SQuInT Program Committee
Postdoctoral Fellows:
Markus Allgaier (UO OMQ)
Sayonee Ray (UNM CQuIC)
Pablo Poggi (UNM CQuIC)
Valerian Thiel (UO OMQ)

SQuInT Event Co-Organizers (Oregon)
Jorjie Arden
Holly Lynn

SQuInT Event Administrator (Oregon)
Brandy Todd

SQuInT Administrator (CQuIC)
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director

Tweet About SQuInT 2020!