Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms

Genetic and Evolutionary Computation Conference (GECCO), pp. 443–452

Abstract

Variational quantum algorithms, such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), have become increasingly popular, offering promising avenues for employing Noisy Intermediate-Scale Quantum devices to address challenging combinatorial optimization tasks like the maximum cut problem. In this study, we utilize an evolutionary algorithm equipped with a unique fitness function. This approach targets hard maximum cut instances within the latent space of a Graph Autoencoder, identifying those that pose significant challenges or are particularly tractable for RQAOA, in contrast to the classic Goemans and Williamson algorithm. Our findings not only delineate the distinct capabilities and limitations of each algorithm but also expand our understanding of RQAOA's operational limits. Furthermore, the diverse set of graphs we have generated serves as a crucial benchmarking asset, emphasizing the need for more advanced algorithms to tackle combinatorial optimization challenges. Additionally, our results pave the way for new avenues in graph generation research, offering exciting opportunities for future explorations.

Authors 6

1. Shuaiqun Pan Aachen

   Leiden University

   Affiliation as printed

   Leiden University, LIACS, Leiden, Netherlands

2. Yash J. Patel Aachen

   Leiden University

   Affiliation as printed

   Leiden University, LIACS, Leiden, Netherlands

   Leiden University, applied Quantum algorithms, Leiden, Netherlands

3. Aneta Neumann

   The University of Adelaide

   Affiliation as printed

   The University of Adelaide, Optimisation and Logistics School of Computer and Mathematical Sciences, Adelaide, Australia

4. Frank Neumann

   The University of Adelaide

   Affiliation as printed

   The University of Adelaide, Optimisation and Logistics School of Computer and Mathematical Sciences, Adelaide, Australia

5. Thomas Bäck Aachen

   Leiden University

   Affiliation as printed

   Leiden University, LIACS, Leiden, Netherlands

6. Hao Wang Aachen

   Leiden University

   Affiliation as printed

   Leiden University, LIACS, Leiden, Netherlands