Empirical performance bounds for quantum approximate optimization*

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.