QAOA Parameter Transferability for Maximum Independent Set using Graph Attention Networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationGraph AttentionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Cross-Problem Parameter Transfer in Quantum Approximate Optimization Algorithm: A Machine Learning Approach
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising candidates to achieve the quantum advantage in solving combinatorial optimization problems. The process of finding a good set of variational …
Combinatorial OptimizationNavigateQuantum Approximation for Multi-Scale Scheduling
This paper proposes a quantum approximate optimization algorithm (QAOA) method for multi-scale wireless scheduling problems. The QAOA is one of the promising hybrid quantum-classical algorithms for many applications and …
SchedulingEvolving a Multi-Population Evolutionary-QAOA on Distributed QPUs
Our research combines an Evolutionary Algorithm (EA) with a Quantum Approximate Optimization Algorithm (QAOA) to update the ansatz parameters, in place of traditional gradient-based methods, and benchmark on the Max-Cut …
Classical symmetries and the Quantum Approximate Optimization Algorithm
We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symm…
Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms
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 device…
BenchmarkingCombinatorial OptimizationGraph Generation