A Hybrid Classical-Quantum Annealing Algorithm for the TSP

본 논문은 그래프 축소 기법을 활용하여 Traveling Salesperson Problem 의 문제 차원을 축소함으로써 D-Wave 어닐러와 같은 현재 양자 장치에서 효율적인 해법을 가능하게 하는 하이브리드 고전-양자 어닐링 알고리즘을 제안하며, 그 성능은 고전 시뮬레이션과 양자 하드웨어를 통해 검증되었다.

핵심

고객을 위해 완벽한 로드 트립을 계획하려는 여행 에이전트라고 상상해 보세요. 고객이 방문하고 싶어 하는 1,000 개의 도시 목록이 있고, 각 도시를 정확히 한 번씩 방문한 후 다시 집으로 돌아오는 가장 짧은 단일 경로를 찾아야 합니다. 이것이 바로 유명한 **외판원 문제 (TSP)**입니다.

문제는 도시의 수가 늘어날수록 가능한 경로의 수가 폭발적으로 증가한다는 점입니다. 이로 인해 세계 최고의 슈퍼컴퓨터조차 절대적으로 최적인 경로를 찾으려다 막히게 됩니다. 마치 매초마다 더 커지는 해변에서 특정 모래알 하나를 찾으려는 것과 같습니다.

이 논문은 고전 컴퓨터(현재 우리가 사용하는 것) 와 양자 컴퓨터(미래 지향적이고 실험적인 것) 의 장점을 결합하여 이 퍼즐을 해결하는 교묘한'팀워크'전략을 제안합니다.

다음은 간단한 비유를 통해 설명한 그들의 방법입니다:

1. 문제: 옵션이 너무 많음

TSP 를 거대하게 엉킨 실뭉치라고 생각해 보세요. 한 번에 전체를 풀려고 하면 불가능합니다. 현재의 양자 컴퓨터는 작고 섬세한 손과 같습니다. 그들은 놀라울 정도로 강력하지만, 한 번에 실의 작은 조각만 잡을 수 있습니다. 1,000 개의 도시로 이루어진 전체 실뭉치를 처리할 수 없습니다. 모든 것을 잡을 만큼 충분한'손가락'(큐비트) 이나 적절한 연결이 없기 때문입니다.

2. 해결책:'확신 있는 척추'

저자들의 비법은 **그래프 축소 (Graph Contraction)**라는 기법입니다. 1,000 개의 도시를 위한 좋은 경로의 아이디어를 각각 스케치하는 500 명의 여행 에이전트 그룹이 있다고 상상해 보세요.

• 풀 (Pool): 이 500 개의 스케치를 모두 모읍니다.
• 패턴 (Pattern): 지도를 자세히 살펴봅니다. 거의 모든 스케치에서 에이전트들이 도시 A 와 도시 B 를 연결하고, 도시 C 와 도시 D 를 연결하는 데 동의한다는 것을 발견합니다. 이것이'확신 있는'연결입니다.
• 단축 (Shortcut): 모든 도시를 별도의 정류장으로 취급하는 대신, 합의된 연결들을'붙여'놓습니다. 긴 도시 사슬 (A-B-C-D) 을 단일한 초대형'메가 도시'로 바꿉니다.

이렇게 하면 목적지를 바꾸는 것이 아니라 지도를 단순화하는 것입니다. 1,000 개의 도시 문제를 50 개의 도시 문제로 바꿀 수 있습니다. 이것이 바로 축소입니다.

3. 양자 단계:'마법 나침반'

이제 지도를 관리 가능한 크기 (예: 50 개 도시) 로 줄였으니, 이 작은 퍼즐을 양자 어닐러(그들이 사용한 D-Wave 기계와 같은) 에 넘깁니다.

• 고전 컴퓨터는 일반적으로 한 경로를 시도하다가 막히면 다른 경로를 시도하는 방식으로 이러한 퍼즐을 해결합니다 (미로 속의 쥐와 같습니다).
• 양자 컴퓨터는'양자 터널링'이라는 현상을 사용합니다. 미로에 쥐가 갇히게 만드는 깊은 계곡이 있다고 상상해 보세요. 양자 컴퓨터는 계곡 벽을 단순히 터널로 뚫고 반대편 출구를 찾을 수 있는 유령과 같습니다.

저자들은 이 양자'유령'능력의 시뮬레이션 (Path Integral Monte Carlo 라고 함) 을 사용하여 축소된 작은 지도에 대한 최선의 경로를 찾았습니다. 지도가 이제 충분히 작아졌기 때문에 양자 컴퓨터가 실제로 이를 효율적으로 해결할 수 있습니다.

4. 결과: 다시 조립하기

양자 컴퓨터가'메가 도시'에 대한 최선의 경로를 찾으면, 알고리즘은 그들을 다시 떼어내어 원래의 1,000 개 도시로 경로를 확장합니다. '붙여'진 부분들이 처음에 발견된 가장 신뢰할 수 있는 연결들이었기 때문에, 최종 경로는 완벽한 해법에 매우 가깝습니다.

그들이 발견한 것은 무엇인가?

이 팀은 실제 여행 데이터 (TSPLIB 라는 라이브러리에서) 로 이를 테스트했습니다:

• 작은 여행: 소규모 도시 그룹의 경우, 그들의 방법은 매번 완벽한경로를 찾았습니다.
• 큰 여행: 거대한 여행 (1,000 개 이상의 도시) 의 경우, 양자 컴퓨터가 처리할 수 있는 크기로 문제를 축소했습니다. 결과적으로 생성된 경로는 매우 좋았습니다 (보통 완벽한 거리의 2~4% 이내). 이는 양자 컴퓨터 단독으로 전체를 해결하려는 시도보다 큰 개선입니다.
• 트레이드오프: 그들은 너무 많은 도시를 붙이면 (너무 공격적으로 행동하면) 실수를 할 위험이 있다는 것을 발견했습니다. 반대로 너무 적게 붙이면 양자 컴퓨터가 여전히 압도당했습니다. 그들은 최상의 결과를 얻기 위해'골디락스'역치를 찾아야 했습니다.

결론

이 논문은 이것이 모든 여행 문제를 즉시 해결한다고 주장하지 않습니다. 대신, 오늘날의 제한된 양자 컴퓨터를 활용하는 실용적인 방법을 보여줍니다. 고전 컴퓨터가 먼저 지도를'단순화'하는 중추적인 작업을 수행하여 관리 가능한 퍼즐을 양자 기계에 넘기면, 양자 컴퓨터는 그 특유의'터널링'능력을 사용하여 거의 완벽한 답을 찾습니다. 고전 컴퓨터가 조직자 역할을 하고 양자 컴퓨터가 마지막의 까다로운 부분을 해결하는 전문가 역할을 하는 하이브리드 팀입니다.

기술 요약

기술적 요약: TSP 를 위한 하이브리드 고전 - 양자 어닐링 알고리즘

문제 정의

외판원 문제 (TSP) 는 완전 가중 그래프에서 최단 해밀턴 순환을 식별해야 하는 근본적인 NP-난해 최적화 문제입니다. 정확한 고전 솔버 (예: Concorde) 는 대규모 인스턴스를 처리할 수 있지만, 다항 시간 내의 확장성 측면에서 종종 어려움을 겪습니다. 반면, 양자 어닐링 (QA) 을 포함한 양자 접근법은 국소 최소값을 탈출하기 위한 열적 잡음에 대한 유망한 대안 메커니즘을 제공합니다. 그러나 현재 D-Wave 어닐러와 같은 잡음이 있는 중규모 양자 (NISQ) 장치는 큐비트 수와 위상적 연결성에 관해 심각한 물리적 한계에 직면해 있습니다. 이러한 제약은 밀집된 연결성이 필요한 대규모 TSP 인스턴스를 기존 양자 처리 장치 (QPU) 에 직접 매핑하는 것을 불가능하게 만듭니다.

방법론

저자들은 대규모 TSP 인스턴스와 현재 양자 하드웨어 능력 사이의 간극을 메우는 하이브리드 고전 - 양자 알고리즘을 제안합니다. 이 접근법은 양자 어닐링의 경로 적분 몬테 카를로 (PIMC) 시뮬레이션과 서브 QUBO 추출 전략이라는 두 가지 근본적인 방법론을 종합합니다.

1. 엣지 빈도를 통한 그래프 축소

핵심 혁신은 원래 문제의 차원을 축소하는 그래프 축소 기법입니다.

• 풀 생성: 알고리즘은 2-opt 이동으로 정제된 시뮬레이션 어닐링 (SA) 을 사용하여 무작위 순열로 후보 솔루션 풀 ($P$) 을 초기화합니다.
• 신뢰할 수 있는 백본 식별: 전체 풀을 분석하는 대신, 알고리즘은 솔루션 집합의 일부 ($S$) 를 샘플링하여 솔루션 전반에 걸쳐 나타나는 엣지의 빈도를 계산합니다. 신뢰 임계값 ($\tau$) 이상으로 나타나는 빈도를 가진 엣지는 "신뢰할 수 있는 백본"으로 식별됩니다.
• 축소: 이러한 고빈도 엣지는 고정되고, 연결된 노드는 "슈퍼 노드"로 병합됩니다. 이는 원래 그래프 $G$ 를 훨씬 작은 서브 TSP 인스턴스 ($G_{sub}$) 로 변환합니다. 서브 문제의 거리 행렬은 슈퍼 노드의 머리 부분과 꼬리 부분과 같은 논리적 경로 병합을 고려하여 재계산됩니다.

2. 하이브리드 최적화 루프

알고리즘은 반복 루프에서 작동합니다:

1. 정제: 고전 휴리스틱이 솔루션 풀을 정제하여 엣지 빈도의 신뢰도를 향상시킵니다.
2. 샘플링 및 축소: 고정될 엣지를 결정하고 그래프를 축소하기 위해 솔루션의 일부가 샘플링됩니다.
3. 양자 해결: 축소된 서브 TSP 는 양자 솔버를 사용하여 해결됩니다. 논문의 실험에서는 다음과 같이 구현되었습니다:
   • 고전 시뮬레이션: 2-opt 이동을 운동 에너지 연산자로 사용하여 TSP 를 제약된 이징과 같은 시스템으로 매핑하는 Martoňák 등 방식에 기반한 경로 적분 몬테 카를로 (PIMC).
   • 하드웨어 실행: D-Wave Advantage_system 4.1 QPU 에서 직접 실행.
4. 확장 및 업데이트: 서브 문제의 솔루션은 고정된 엣지를 다시 삽입하여 원래 그래프로 확장됩니다. 새로운 투어는 풀에 추가되며, 개선이 발견되면 전역 최적해가 업데이트됩니다.
5. 종료: $K$ 번의 연속된 반복에서 개선이 없을 때까지 이 과정이 반복됩니다.

주요 기여

• 확장 가능한 하이브리드 프레임워크: 이 논문은 NISQ 장치의 큐비트 및 연결성 한계를 우회하여 대규모 TSP 인스턴스를 현재 하드웨어가 관리할 수 있는 크기로 축소하는 방법을 제시합니다 (예: 1,002 개 도시 인스턴스를 약 185 개 노드로 축소).
• PIMC 와 서브 QUBO 의 통합: 이 작업은 복잡한 에너지 지형을 탐색하는 데 효과적인 PIMC 양자 터널링의 이론적 가능성과 서브 QUBO 추출 (반복적 문제 분할) 의 실용적 필요성을 결합합니다.
• 하드웨어에서의 실증적 검증: 저자들은 D-Wave 양자 어닐러에서 알고리즘을 성공적으로 시연하여, 축소 전략이 그렇지 않으면 해결 불가능한 TSP 서브 문제의 직접 임베딩을 가능하게 함을 보여주었습니다.

실험 결과

이 알고리즘은 14 개에서 11,849 개까지의 도시가 포함된 TSPLIB 인스턴스에서 평가되었습니다.

• 매개변수 민감도:
  • 임계값 ($\tau$): $\tau$를 낮추면 압축이 증가하여 문제 크기가 줄어들지만, 하위 최적 엣지를 고정할 위험이 있어 최적성 간극이 커질 수 있습니다. $\tau=0.75$ 임계값은 중간 크기 인스턴스에 유리한 균형을 제공했습니다.
  • 풀 크기 ($N_I$) 및 샘플 크기 ($N_S$): 500 의 풀 크기와 250(50%) 의 샘플 크기는 중간에서 대규모 인스턴스에 대해 가장 좋은 결과를 산출했으며, 이는 확률적 샘플링이 엣지 선택이 과도하게 결정론적이 되는 것을 방지함을 시사합니다.
• 고전 기준 대비 성능:
  • 작은 인스턴스 (예: burma14, ulysses22) 의 경우, 알고리즘은 전역 최적해 (0% 간극) 를 찾았습니다.
  • 큰 인스턴스 (예: pr2392) 의 경우, 알고리즘은 평균 최적성 간극을 4% 미만으로 유지하여 여러 경우 Google 의 OR-Tools 보다 우수한 성능을 보였습니다 (예: rl11849는 OR-Tools 의 14.58% 대비 7.36% 간극 달성).
• D-Wave 하드웨어 결과:
  • D-Wave QPU 에서 실행되었을 때, 하이브리드 접근법은 D-Wave 네이티브 BQM 하이브리드 솔버보다 훨씬 더 나은 최적성 간극을 달성했습니다. 예를 들어, ulysses22에서 제안된 방법은 약 5 개 노드만의 서브 문제를 해결함으로써 하이브리드 솔버의 16.88% 대비 2.57% 간극을 달성했습니다.
• 병목 현상:
  • PIMC 시뮬레이션 단계는 고전 시뮬레이션에서 주요 계산 병목 현상으로 확인되었습니다.
  • 매우 큰 인스턴스 (예: rl11849) 의 경우, 고전 오버헤드 (풀 초기화 및 정제) 가 지배적이 되어 실행 시간의 약 70% 를 차지했으며, 이는 극단적인 규모에서 양자 가속의 이점이 고전 전처리 비용에 의해 상쇄됨을 시사합니다.

중요성 및 주장

이 논문은 하이브리드 기법이 현재 양자 장치의 물리적 한계를 효과적으로 완화한다고 주장합니다. 그래프 축소를 위해 고전 최적화를 활용함으로써 저자들은 다음을 입증합니다:

1. 실현 가능성: 대규모 TSP 인스턴스는 고품질 솔루션에 필요한 구조적 무결성을 잃지 않고 NISQ 어닐러에 임베딩하기에 적합한 규모로 축소될 수 있습니다.
2. 양자 우위 잠재력: 현재 PIMC 시뮬레이션은 고적이지만, 이 프레임워크는 양자 하드웨어에 직접 적용 가능하도록 설계되었습니다. 결과는 PIMC 단계가 양자 어닐러에서 실행된다면 계산 비용이 극적으로 감소하여 최적화 단계에서 기하급수적인 속도 향상을 제공할 가능성을 시사합니다.
3. 견고성: 이 방법은 다양한 인스턴스 크기에 걸쳐 견고하여 작은 문제에서는 정확한 솔루션을 달성하고, 고전 휴리스틱이 어려움을 겪는 대규모 문제에서는 낮은 최적성 간극을 유지합니다.

저자들은 대규모 인스턴스의 경우 고전 오버헤드가 여전히 과제이지만, 제안된 축소 전략이 TSP 를 현재 양자 어닐링 기술의 범위에 성공적으로 끌어와 조합 최적화를 위한 하이브리드 고전 - 양자 접근법의 타당성을 검증했다고 결론지었습니다.