Empirical performance bounds for quantum approximate optimization
ORAL
Abstract
The quantum approximate optimization algorithm (QAOA) is a promising application for near-term intermediate-scale quantum (NISQ) computers to solve combinatorial optimization problems. However, it is unclear how QAOA performance varies for different problem instances corresponding to different graphs. We numerically simulated pure-state QAOA on the MaxCut problem for instances on every connected non-isomorphic graph with nine or fewer vertices with up to three layers of QAOA unitary operations. We find the expectation values for the approximation ratios are not very sensitive to graph structure, with distributions over the sets of graphs that narrow as the number of QAOA layers increases. In contrast, the probability of obtaining the optimal result from QAOA is much more sensitive to graph structure, with distributions over different graphs that widen with additional QAOA layers. The results provide performance bounds for NISQ computers and suggest future directions for using relationships between graph structure and performance to identify specific types of problems that are best suited for QAOA.
–
Presenters
-
Phillip Charles Lotshaw
Oak Ridge National Laboratory, Quantum Computational Sciences Group, Oak Ridge National Laboratory
Authors
-
Phillip Charles Lotshaw
Oak Ridge National Laboratory, Quantum Computational Sciences Group, Oak Ridge National Laboratory
-
Travis S Humble
Oak Ridge National Lab, Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge National Laboratory, Quantum Computational Sciences Group, Oak Ridge National Laboratory, University of Tennessee
-
Rebekah Herrman
University of Tennessee, Department of Industrial and Systems Engineering, University of Tennessee at Knoxville
-
James Ostrowski
University of Tennessee, Department of Industrial and Systems Engineering, University of Tennessee at Knoxville