Quantum approximate optimization algorithms for maximum cut on low-girth graphs

Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the quantum approximate optimization algorithm (QAOA) for solving the MaxCut problem. Its guarantee on the cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs, which are outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell, known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in the ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare the best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms these best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases in which ma-QAOA exhibits superiority over the best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs, such as tiling grid graphs, where QAOA also demonstrates an advantage.