Impact of Graph Structures for QAOA on MaxCut

Understand

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 graphs, however, little is known about the algorithm on arbitrary graphs.
• We evaluate the performance of QAOA at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices and analyze how graph structure affects QAOA performance.
• Some of the strongest predictors of QAOA success are the existence of odd-cycles and the amount of symmetry in the graph.