Projecting NISQ-era quantum advantage with QAOA

A major milestone in quantum computing research is the demonstration of quantum supremacy, where some computation is performed by a quantum computer that is unfeasible classically. Recently, the efforts culminated in the experiment by Google's quantum teams and collaborators of sampling from random circuits. However, it is important to recognize that supremacy demonstrations based on artificial tasks bring very limited advantage for practical applications. A common problem used in benchmarking high performance computing is MaxCut, with applications in domains such as machine scheduling, image recognition, electronic circuit layout, and others. Maxcut has been used extensively, both theoretically and experimentally, to assess the performance of the hybrid Quantum Approximate Optimization Algorithm (QAOA), one of the leading candidates to demonstrate quantum advantage in the NISQ era. Here we project the performance of QAOA by considering the challenges due to its variational and stochastic nature and compare it with several among the best performing classical solvers in terms of time to solution and quality. The results demonstrate the importance of algorithm and problem selection and we discuss the performance data in the context of projecting NISQ-era quantum advantage.