QAOA Performance Benchmarks using Max-Cut

The Quantum Approximation Optimization Algorithm (QAOA) is an algorithm proposed to solve combinatorial optimization problems such as Max-Cut on near-term quantum computing hardware. In this talk we present benchmark data comparing the performance of QAOA in solving the Max-Cut problem with the performance of its classical counterpart, the Goemans-Williamson algorithm. With a simulator of an N-qubit quantum computer we use QAOA to approximate Max-Cut solutions for all N-vertex fully connected graphs up to N=8 and compare the distribution of the derived approximation ratios with the cited typical approximation ratio obtained with the Goemans-Williamson algorithm. We investigate the dependency of QAOA performance on multiple parameters and determine the percentage of graphs for which QAOA outperforms the Goemans-Williamson bound.