Steiner Traveling Salesman Problem with Quantum Annealing
Created by
- Haebom
Category
Empty
저자
Alessia Ciacco, Francesca Guerriero, Eneko Osaba
개요
본 논문은 Steiner Traveling Salesman Problem (STSP)에 대한 양자 어닐링 기반 해결책을 제시한다. STSP는 기존의 Traveling Salesman Problem(TSP)에 Steiner node(경로에 추가하여 전체 비용을 최소화할 수 있는 추가 노드)를 포함하는 변형 문제이다. NP-hard 문제인 STSP를 해결하기 위해 D-Wave의 양자 어닐링 하드웨어를 활용하고, 계산 가능성을 높이기 위한 전처리 방법(네트워크 크기 감소)을 개발하였다. 실험 결과, 이 전처리 기법은 문제의 복잡도를 크게 줄여 Quadratic Unconstrained Binary Optimization (QUBO)를 양자 어닐링 하드웨어에 더 적합하게 만들었으며, 양자 어닐링이 STSP 해결에 유용한 접근법임을 보여준다.
시사점, 한계점
•
시사점:
◦
양자 어닐링을 활용하여 STSP를 해결하는 새로운 접근법을 제시하였다.
◦
전처리 기법을 통해 양자 어닐링 하드웨어의 계산 가능성을 향상시켰다.
◦
실험 결과를 통해 양자 어닐링의 STSP 해결 가능성을 확인하였다.
•
한계점:
◦
제안된 전처리 기법의 일반화 가능성 및 성능 한계에 대한 추가 연구가 필요하다.
◦
D-Wave 하드웨어에 특화된 접근법으로 다른 양자 컴퓨팅 플랫폼으로의 확장성 검토가 필요하다.
◦
대규모 STSP 문제에 대한 해결 성능 및 확장성에 대한 추가적인 실험 및 분석이 필요하다.
