Impact of Graph Structure for QAOA Performance on MaxCut*

The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on specific families of regular graphs but little is known about the algorithm on arbitrary ones. The lack of comprehensive study may hide insight on QAOA performance. We evaluate the performance of QAOA at depths one, two, and three on the MaxCut problem for all graphs with at most eight vertices and analyze how graph structure affects QAOA. To do this, we examine correlations between graph properties and metrics associated with QAOA performance. We find that the number of edges and clique number have a strong positive correlation to the expected value of the cost operator C while diameter and number of cut vertices have strong negative correlations. Interestingly, while group size and the number of orbits are closely related, the number of orbits tends to correlate better with the expected value and a quantity we call the gap. Knowing how graph structure positively or negatively impacts performance can allow us to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.