Emulating QAOA via Graph Neural Networks
Paolo Zentilini, Sebastiano Corli, Enrico Prati · 2024
The MaxCut is a combinatorial problem consisting of finding the best sub-partitions of a graph, in order to maximize the value of a tailored-suited cost function. Although such specific problem belongs to the NP-hard class, quantum computing could lower the underlying computational complexity. The paramount quantum algorithm in literature to tackle the MaxCut is the QAOA, a trotterized version of adiabatic computation. Within such formulation, the cost function is encoded by a target Hamiltonian, whose spectrum matches the energy landscape to be handled by an optimization process. In the field of classical machine learning, a recent tool introduced to deal with graphs is provided by Graph Neural Networks (GNNs), whose peculiar architecture allows graph data to be embedded into Euclidean spaces, exploiting their topological structure as an intrinsic feature. We exploit the predictive power of GNNs, in order to classically emulate the energy landscape of the QAOA target Hamiltonian. In order to assess the predictive capacity of GNNs, we trained our model on graphs scaling from 3 to 12 vertices and achieving an accuracy between 0.9 and 0.99. We trained and tested the models on different topologies to assure the algorithm performances do not depend on the specific instance of the problem. Furthermore, the trained model proves to extend the correctness of the predictions for graphs up to 20 vertices still keeping a high accuracy. Such result envisages further development by exploiting HPC infrastructures and adapting warm starting techniques.