Quantum computing has the potential to provide speedups over classical state-of-the-art for some combinatorial optimization problems. Recent advances in both hardware and algorithm development have made it possible to solve small problems on modern quantum computers. Combinatorial optimization problems (especially NP-hard problems) are of particular interest, since for many of these problems best classical algorithms cannot provide solutions of sufficient quality in reasonable time.

In this talk, I will provide an overview of our efforts on improving the performance of Quantum Approximate Optimization Algorithm (QAOA) and on applying QAOA to problems of practical size using problem-decomposition schemes. I will discuss the potential for quantum advantage with QAOA on graph problems, as well as the limitations of the state-of-the-art approaches.