Data-Driven Quantum Approximate Optimization Algorithm (QAOA) for Max-Cut Problems

We present a data-driven QAOA for the Max-Cut problem over generic weighted graphs, which can avoid the expensive optimization effort for its quantum circuit parameters. In data-driven QAOA, a parameter transfer strategy based on graph density can provide quasi-optimal parameters from previous instances with similar properties in a database prepared in advance. The quasi-optimal parameters can be directly used to obtain a good cut or be a good initial guess for significantly saving optimization time. Moreover, as running cases increase, the database grows and can provide more effective parameters. We numerically verified the strategy on 1710 random instances on IBM simulators with perfect quantum gates. We also simulated the algorithm on 3 practical graphs in the power system with a realistic noise model and observed good approximation results on the Max-Cut problem. It is encouraging that, without any parameter optimization, the proposed data-driven QAOA is competitive with the famous classical algorithm, the Goemans-Williamson algorithm.