We will discuss methods to determine how good of an approximation can be achieved with the QAOA algorithm applied to local variants of classical NP-hard problems. In particular, while the performance of QAOA has been extensively studied for MAxCut, nothing is known for its local counterpart, LocalMaxCut. With this work, we wanted to initiate the study of QAOA on local problems, which we believed might be better suited for local quantum algorithms to outperform classical ones. Preliminary results show that if quantum supremacy is to be achieved, it would be on complex graphs. We show that the local algorithms for LocalMaxCut still outperform QAOA on simple graph instances and discuss future directions.
Copyright. All Rights Reserved.