Southwest Quantum Information and Technology

Investigating the quantum approximate optimization algorithm's advantage over classical algorithms

Presenting Author: Ciaran Ryan-Anderson, CQuIC New Mexico, Sandia
Contributing Author(s): Yang Jiao and Ojas Parekh

The Quantum Approximate Optimization Algorithm (QAOA) is designed to find approximate solutions to combinatorial optimization problems. The approximation quality of QAOA is a function of the parameters to the algorithm, one of which corresponds to the depth of a quantum circuit realizing QAOA. Recently, in [1], it has been shown that even when QAOA is used in its lowest-depth form, it can produce distributions that are hard to sample from classically. This indicates that QAOA can demonstrate some level of ``Quantum Supremacy," at least for the task of sampling from a distribution. However, QAOA is foremost an optimization algorithm, and QAOA's complexity as an optimization algorithm is largely open. In this work we investigate QAOA's advantage over classical algorithms from an optimization perspective. This work was supported by the Laboratory Directed Research and Development (LDRD) program at Sandia National Laboratories. Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000. [1] E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm, (2016), arXiv:1602.07674.

(Session 9c : Friday from 4:15pm - 4:45pm)