用进化算法生成难解图，测试量子优化算法极限
Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms
- 用图自编码器潜空间+进化算法生成挑战性最大割实例
- 发现RQAOA在部分图上表现优于经典算法，但存在明显瓶颈
- 生成的图集可作新基准，适合量子优化研究者参考
变分量子算法（如递归量子近似优化算法RQAOA）日益受到关注，为利用噪声中等规模量子设备解决最大割等组合优化难题提供了可能。本文采用一种配备独特适应度函数的进化算法，在图自编码器的潜空间中寻找对RQAOA具有挑战性的最大割实例，相较经典Goemans-Williamson算法展现不同性能边界。研究不仅揭示了两类算法的能力与局限，还拓展了对RQAOA适用范围的理解。所生成的一组多样化图结构可作为重要基准，凸显开发更先进算法的必要性，并为图生成研究开辟新方向。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。