On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
Published in Arxiv preprint 2408.15413, 2024
Recommended citation: Leonardo Lavagna, Simone Piperno, Andrea Ceschini, Massimo Panella: On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA. Arxiv preprint 2408.15413 (2024). https://www.arxiv.org/abs/2408.15413
We study the Quantum Approximate Optimization Algorithm (QAOA) to solve the MaxCut problem on graphs focusing on the relationship between graph symmetries, its perturbations, and the approximation ratio achieved by the QAOA. The main focus is to leverage symmetries in the graph to gain in approximation ratio, by studying simple graph perturbations in terms of the corrisponding automorphism groups and spectral properties. This article fits into a program where we would like to find a functional relationship (and its properties) between the approximation ratio achieved by the QAOA and a perturbation $f(G)$ of a graph $G$, where $f\in Aut(G)$. Here we show some heuristic results that point in the direction of the existence of such an $f$ and on some of its properties (i.e. its independence on the number of layers $p$).