Southwest Quantum Information and Technology

Numerical evidence for exponential speed-up of QAOA over unstructured search for approximate constrained optimization

Presenting Author: Andreas Bärtschi, Los Alamos National Laboratory
Contributing Author(s): John Golden, Stephan Eidenbenz, Daniel O'Malley

We present numerical evidence for an exponential speed-up of a Quantum Alternation Operator Ansatz (QAOA) over Grover-style unstructured search in finding approximate solutions to constrained optimization problems. To this end, we conduct a comprehensive numerical study on several Hamming-weight constrained optimization problems (Max-k-VertexCover, Densest-k-Subgraph, Max-Bisection) for which we include combinations of all standardly studied mixer and phase separator Hamiltonians (Ring mixer, Clique mixer, Objective Value phase separator) as well as quantum minimum-finding inspired Hamiltonians (Grover mixer, Threshold-based phase separator). We identify Clique-ObjValue-QAOA with an exponential speedup over Grover-Threshold-QAOA in terms of the number of rounds necessary to reach an approximation ratio of 99%, with all other QAOA combinations coming in at a distant third. For Max-k-VertexCover and Densest-k-Subgraph we also give an efficient gradient descent based angle finding strategy. For comparison, we tie Grover-Threshold-QAOA's scaling in terms of the number of rounds necessary to sample high-value solutions to the same asymptotic behavior as that of unstructured search. Our result suggests that maximizing QAOA performance requires a judicious choice of mixer and phase separator, and should trigger further research into other QAOA variations.

Read this article online: https://arxiv.org/abs/2202.00648

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