Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era.
Quantifying the performance of QAOA in the near-term regime is of utmost importance. A team at Argonne National Laboratory and Clemson University in USA has performed a large-scale numerical study of the approximation ratios attainable by QAOA.
To find good QAOA parameters they performed 990 million 10-qubit QAOA circuit evaluations. The researchers found that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. They observed a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. They also discovered that the difference in approximation ratios between problem instances increases as the similarity between instances decreases.
