用图注意力网络迁移量子参数，高效求解大规模独立集问题
QAOA Parameter Transferability for Maximum Independent Set using Graph Attention Networks
- 用GAT学习小图最优参数，迁移到大图
- 在数千顶点图上表现媲美顶尖经典算法
- 适合量子计算初学者和优化研究者
量子近似优化算法（QAOA）是解决组合优化问题的有前景的变分量子方法。在QAOA中，需通过求解一系列非线性、非凸优化问题来优化变分参数。本文提出一种基于图注意力网络（GAT）的QAOA参数迁移方案，用于求解最大独立集（MIS）问题。我们预先为12和14个顶点的图准备了优化参数，并利用GAT将这些参数迁移到更大规模的图上。此外，我们设计了一种混合分布式资源感知算法（HyDRA-MIS），将大规模问题分解为可在噪声中等规模量子（NISQ）设备上运行的小问题。将基于GAT的参数迁移方法集成到HyDRA-MIS中，在包含数千个顶点的图上表现出与当前最先进的经典MIS求解器KaMIS相当的结果。
原文摘要 · Abstract (English)
The quantum approximate optimization algorithm (QAOA) is one of the promising variational approaches of quantum computing to solve combinatorial optimization problems. In QAOA, variational parameters need to be optimized by solving a series of nonlinear, nonconvex optimization programs. In this work, we propose a QAOA parameter transfer scheme using Graph Attention Networks (GAT) to solve Maximum Independent Set (MIS) problems. We prepare optimized parameters for graphs of 12 and 14 vertices and use GATs to transfer their parameters to larger graphs. Additionally, we design a hybrid distributed resource-aware algorithm for MIS (HyDRA-MIS), which decomposes large problems into smaller ones that can fit onto noisy intermediate-scale quantum (NISQ) computers. We integrate our GAT-based parameter transfer approach to HyDRA-MIS and demonstrate competitive results compared to KaMIS, a state-of-the-art classical MIS solver, on graphs with several thousands vertices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。