Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms
Created by
Haebom
저자
Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Back, Hao Wang
개요
본 연구는 Recursive Quantum Approximate Optimization Algorithm (RQAOA)와 같은 변분 양자 알고리즘을 이용하여 최대 절단 문제와 같은 어려운 조합 최적화 문제를 해결하는 데 중점을 둡니다. Graph Autoencoder의 잠재 공간 내에서 어려운 최대 절단 문제 인스턴스를 식별하기 위해 독특한 적합도 함수를 갖춘 진화 알고리즘을 사용하여 RQAOA와 고전적인 Goemans-Williamson 알고리즘의 성능을 비교 분석합니다. 이를 통해 각 알고리즘의 강점과 한계를 명확히 밝히고 RQAOA의 작동 한계에 대한 이해를 높이며, 생성된 다양한 그래프는 조합 최적화 문제 해결을 위한 더욱 발전된 알고리즘의 필요성을 강조하는 벤치마킹 자원으로 활용됩니다. 또한, 그래프 생성 연구에 대한 새로운 가능성을 제시합니다.
시사점, 한계점
•
시사점:
◦
RQAOA와 고전 알고리즘의 상대적 강점과 약점을 명확하게 보여줍니다.
◦
RQAOA의 성능 한계를 이해하는 데 기여합니다.
◦
조합 최적화 문제를 위한 새로운 벤치마킹 데이터셋을 제공합니다.
◦
그래프 생성 연구에 새로운 방향을 제시합니다.
•
한계점:
◦
연구에서 사용된 진화 알고리즘 및 Graph Autoencoder의 특성이 결과에 미치는 영향에 대한 자세한 분석이 부족할 수 있습니다.
