# Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms

arXiv: https://arxiv.org/abs/2502.12012 · HTML: https://mlsanity.com/paper/2502.12012/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 63 references that are in the map.
- First posted on arXiv 30 Jan 2025.

## Builds on (most cited first, 17 of 17)

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [Evaluation of a Tree-based Pipeline Optimization Tool for Automating Data Science](https://mlsanity.com/paper/1603.06212/) (2016)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [CMA-ES for Hyperparameter Optimization of Deep Neural Networks](https://mlsanity.com/paper/1604.07269/) (2016)
- [Benchmarking in Optimization: Best Practice and Open Issues](https://mlsanity.com/paper/2007.03488/) (2020)
- [Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning](https://mlsanity.com/paper/2104.09856/) (2021)
- [Evolutionary Diversity Optimization Using Multi-Objective Indicators](https://mlsanity.com/paper/1811.06804/) (2018)
- [Reinforcement Learning Assisted Recursive QAOA](https://mlsanity.com/paper/2207.06294/) (2022)
- [Feature-Based Diversity Optimization for Problem Instance Classification](https://mlsanity.com/paper/1510.08568/) (2015)
- [Classical algorithms and quantum limitations for maximum cut on high-girth graphs](https://mlsanity.com/paper/2106.05900/) (2021)
- [Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem](https://mlsanity.com/paper/2405.18772/) (2024)

## Abstract (arXiv)

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.