Solving the Traveling Salesman Problem via Different Quantum Computing Architectures
Created by
- Haebom
Category
Empty
저자
Venkat Padmasola, Zhaotong Li, Rupak Chatterjee, Wesley Dyk
개요
본 논문은 등장하는 광자 및 양자 컴퓨팅 아키텍처를 잘 알려진 NP-hard 최적화 문제인 외판원 순회 문제(TSP)에 적용하는 것을 연구합니다. 시뮬레이티드 어닐링(SA), 양자 어닐러와 광학 코히어런트 이징 머신(Optical Coherent Ising Machines)에 구현된 이차 비구속 이진 최적화(QUBO-Ising) 방법, 그리고 게이트 기반 양자 컴퓨터에서의 양자 근사 최적화 알고리즘(QAOA)과 양자 위상 추정 알고리즘(QPE) 등 여러 접근 방식을 조사합니다. IBM 양자 플랫폼에서 QAOA와 QPE를, D-Wave 양자 어닐러와 비선형 광전자 이징 머신인 QCI Dirac 머신을 사용하여 QUBO-Ising 방법을 탐구했습니다. 게이트 기반 양자 컴퓨터는 시뮬레이션에서 작은 TSP 인스턴스에 대해 정확한 결과를 보여주었지만, 실제 양자 장치는 노이즈와 제한된 확장성으로 인해 방해를 받습니다. 회로 복잡성은 문제 크기와 함께 증가하여 최대 6개 노드의 TSP 인스턴스로 성능이 제한됩니다. 반대로, 이징 기반 아키텍처는 더 큰 문제 크기에 대해 향상된 확장성을 보여줍니다. SQUID 기반 이징 머신은 최대 12개 노드의 TSP 인스턴스를 처리할 수 있으며, 비선형 광전자 이징 머신은 이 기능을 18개 노드로 확장합니다. 그러나 문제 크기가 증가함에 따라 하드웨어 제한과 기저 상태 수렴 달성의 어려움으로 인해 해는 비최적 경향을 보입니다. 이러한 한계에도 불구하고 이징 머신은 기존 방법보다 상당한 시간적 이점을 보여주어 대규모 TSP를 효율적으로 해결하기 위한 유망한 후보가 됩니다.
시사점, 한계점
•
시사점:
◦
이징 기반 아키텍처(특히 광학 코히어런트 이징 머신)는 게이트 기반 양자 컴퓨터보다 더 큰 TSP 문제에 대해 확장성이 뛰어납니다.
◦
이징 머신은 기존 방법보다 TSP 문제 해결에 상당한 시간적 이점을 제공합니다.
◦
게이트 기반 양자 컴퓨터는 작은 TSP 인스턴스에 대해 정확한 결과를 제공하지만, 노이즈와 확장성 문제가 존재합니다.
•
한계점:
◦
게이트 기반 양자 컴퓨터의 회로 복잡성은 문제 크기에 따라 기하급수적으로 증가하여 작은 문제(최대 6 노드)에만 적용 가능합니다.
◦
이징 머신은 하드웨어 한계와 기저 상태 수렴의 어려움으로 인해 비최적 해를 제공할 수 있습니다.
◦
이징 머신의 확장성에도 불구하고, 매우 큰 문제에 대한 해결 능력은 여전히 제한적입니다.
