Evaluation of QAOA based on the approximation ratio of individual samples

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors, it is one of the promising candidates likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, for exact, approximate and heuristic solution. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.