QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling

이 논문은 좌표 하강법을 사용하여 복잡한 드론 스케줄링 문제를 관리 가능한 하위 문제로 분해하는 확장 가능한 양자 최적화 접근법인 QUACOD을 소개하며, 이는 현재 제한된 큐비트 하드웨어에서 효과적인 해결책을 가능하게 하면서 기존 방법들보다 효율성과 확장성 측면에서 크게 우수한 성능을 발휘합니다.

핵심

수백 대의 배송 드론으로 구성된 거대한 함대의 관리자라고 상상해 보세요. 수백 개의 택배를 배달해야 하지만, 드론에는 한 가지 제약이 있습니다. 영원히 날 수 없다는 것이죠. 드론은 착륙하여 배터리를 재충전하고 새로운 택배를 받아야 합니다. 목표는 간단하지만 까다롭습니다. 모든 택배를 가능한 한 빠르게 배달하고, 다른 드론이 여전히 작업하는 동안 어떤 드론도 기다리게 하지 않도록 하는 것입니다.

이것이 바로 드론 스케줄링 문제입니다. 이는 모든 사람이 서로 다른 동작을 하는 혼란스러운 춤을 조직하려는 것과 같습니다. 마지막 무용수가 춤을 마치자마자 음악이 멈추기를 원하죠.

문제: 너무 많은 무용수와 너무 작은 무대

실제 세계에서는 수백 대의 드론을 위한 완벽한 일정을 짜는 것이 컴퓨터에게 악몽과 같습니다. 이는 수학 퍼즐이 너무 복잡하여 세계 최고의 슈퍼컴퓨터조차도 이를 해결하는 데 어려움을 겪습니다.

최근 과학자들은 "양자 컴퓨터를 사용해 보자!"라고 생각했습니다. 이는 기존 컴퓨터보다 특정 퍼즐을 훨씬 빠르게 해결할 수 있는 미래지향적인 기계입니다. 그러나 한 가지 함정이 있습니다. 현재의 양자 컴퓨터는 작고 fragile한 악기 같습니다. 소수의 '큐비트'(양자 버전의 뇌세포) 만을 보유하고 있을 뿐입니다. 이러한 양자 컴퓨터로 거대한 드론 문제를 해결하려는 것은 신발 상자 안에 전체 오케스트라를 넣으려는 것과 같습니다. 현재의 양자 하드웨어는 전체 문제를 한 번에 처리할 만큼 충분히 크지 않습니다.

해결책: QUACOD(조각화 전략)

Van-Quang-Huy Nguyen 과 동료들이 이끄는 이 논문의 저자들은 QUACOD(좌표 하강을 통한 양자 최적화) 라는 영리한 우회책을 고안해냈습니다.

QUACOD 를 양자 컴퓨터가 한 번에 전체 팀을 처리하기에 너무 작다는 것을 아는 스마트한 프로젝트 매니저라고 생각하세요. 100 대의 드론을 동시에 스케줄링하려고 시도하는 대신, QUACOD 는 문제를 작고 관리 가능한 조각으로 나눕니다.

간단한 비유를 들어 작동 방식을 살펴보겠습니다.

1. 초점 그룹 접근법: 100 대의 드론으로 구성된 거대한 팀이 있다고 가정해 보세요. QUACOD 는 양자 컴퓨터에게 100 대를 한 번에 스케줄링하라고 요청하지 않습니다. 대신 5 대의 드론과 10 개의 경로로 구성된 작은 '초점 그룹'을 선택합니다.
2. 양자 스프린트: 양자 컴퓨터에는 이 작은 그룹만 보냅니다. 양자 컴퓨터는 이 5 대의 드론을 스케줄링하는 최선의 방법을 빠르게 찾아냅니다.
3. 좌표 하강 루프: 양자 컴퓨터가 작업을 마치면, QUACOD 는 해당 5 대의 드론을 고정합니다. 그런 다음 다른 작은 드론 그룹 (아마도 5 대의 다른 드론) 을 선택하여 양자 컴퓨터로 보냅니다.
4. 과정 반복: 서로 다른 드론 그룹을 교체하며 이 과정을 반복합니다. 라디오를 조정하여 정적 잡음이 사라지듯, 매 라운드마다 전체 일정이 조금씩 개선됩니다.

거대한 문제를 작은 '좌표'(작은 변수 그룹) 로 분할함으로써 QUACOD 는 작은 양자 컴퓨터가 혼자서는 처리할 수 없었던 거대한 문제를 해결할 수 있게 합니다.

결과: 경쟁사 제압

이 팀은 QUADRO 라는 이전 최우수 방법과 QUACOD 를 비교 테스트했습니다. 그들이 발견한 바는 다음과 같습니다.

• 속도와 효율성: QUACOD 는 기존 방법보다 더 빠르게 완료되는 일정을 찾았습니다.
• **확장성 (큰 승리): 기존 방법 (QUADRO) 은 약 11 대의 드론만 처리할 수 있었습니다. 반면, 동일한 작은 양자 '신발 상자'를 사용하는 QUACOD 는 55 대의 드론 (5 배 더 많음) 과 1,000 개의 경로 (35 배 더 많음) 로 구성된 문제를 성공적으로 관리했습니다.
• 하드웨어 효율성: 거대하고 완벽한 양자 컴퓨터가 필요하지 않음을 입증했습니다. 올바른 전략 (그들의 '하드웨어 효율적' 회로 설계와 같은) 을 사용하면 오늘날 우리가 가진 작고 '노이즈가 있는' 양자 컴퓨터로도 충분합니다.

결론

이 논문은 QUACOD 가 교량 역할을 한다고 주장합니다. 이는 양자 컴퓨팅의 힘을 실용화하여 오늘날 제한된 기술로도 실시간 물류 문제에 적용 가능하게 합니다. 이는 우주의 모든 물류 문제를 해결할 것을 약속하지는 않지만, 큰 문제를 작은 조각으로 분할함으로써 오늘날의 작은 양자 컴퓨터로 이전에는 불가능했던 작업을 수행할 수 있음을 증명합니다.

간단히 말해: QUACOD 는 작은 양자 컴퓨터가 거대한 양자 컴퓨터처럼 행동할 수 있게 하는 스마트한 전략으로, 드론 배송을 이전보다 더 빠르고 효율적으로 스케줄링할 수 있게 해줍니다.

기술 요약

기술 요약: QUACOD – 확장 가능한 드론 스케줄링을 위한 좌표 하강 기반 양자 최적화

1. 문제 정의

본 논문은 드론 스케줄링 문제를 다루며, 이는 라스트마일 물류의 핵심 요소로, 전체 드론 부대의 최대 완료 시간($C_{max}$)을 최소화하기 위해 미리 계산된 경로를 동일한 드론 부대에 할당하는 것을 목표로 합니다.

문제의 주요 제약 조건 및 특성은 다음과 같습니다:

• 배터리 제약: 드론은 연속된 경로 사이에 재충전을 해야 하며, 이는 총 완료 시간에 상당한 영향을 미치는 무시할 수 없는 재충전 시간($c$)을 도입합니다.
• 조합적 복잡성: 이 문제는 외판원 문제 (Traveling Salesman Problem) 와 관련이 있는 NP-난해 (NP-hard) 문제이며, 경로 수 ($n$) 와 드론 수 ($q$) 가 증가함에 따라 해 공간이 기하급수적으로 확장됩니다.
• 하드웨어 제한: 현재의 잡음이 있는 중규모 양자 (NISQ) 장치는 대규모 스케줄링 문제를 양자 어닐링이나 변분 양자 알고리즘 (VQA) 에 직접 인코딩하는 데 필요한 큐비트 수를 갖추지 못해 실용적 적용이 어렵습니다. QUADRO 와 같은 기존 양자 접근법은 매우 작은 사례 (예: 11 대 미만의 드론) 에만 제한됩니다.

2. 방법론: QUACOD

저자들은 엄격한 큐비트 제약 하에서 대규모 스케줄링 문제를 해결하기 위해 설계된 하이브리드 양자 - 고전 프레임워크인 **QUACOD(좌표 하강을 통한 양자 최적화)**를 제안합니다.

A. 문제 공식화 및 QUBO 변환

스케줄링 문제는 각 경로가 정확히 하나의 드론에 할당되도록 하는 할당 제약과 용량 제약 하에서 $C_{max}$를 최소화하는 것으로 초기 모델링됩니다. 이를 양자 최적화와 호환되도록 하기 위해 저자들은 문제를 2 차 무제약 이진 최적화 (QUBO) 형식으로 변환합니다:

1. 제약 조건 처리: 등식 제약 (경로 할당) 은 목적 함수에 추가되는 페널티 항으로 변환됩니다.
2. 목적 함수 변환: $C_{max}$를 직접 최소화하는 대신, 저자들은 개별 드론 완료 시간 ($T_j$) 의 평균 완료 시간 ($T/q$) 으로부터의 편차 제곱합을 최소화하는 것이 $C_{max}$를 효과적으로 최소화한다는 관찰에서 도출된 휴리스틱을 활용합니다. 이를 통해 복잡한 부등식 제약이 제거됩니다.
3. 최종 목적 함수: 결과적으로 생성된 QUBO 함수는 $T_j$의 편차 제곱합과 할당되지 않은 경로에 대한 페널티를 최소화합니다.

B. QUACOD 알고리즘

큐비트 부족이라는 한계를 극복하기 위해 QUACOD 는 좌표 하강 (Coordinate Descent) 최적화 전략을 적용합니다:

• 분해: 모든 $n \times q$개의 이진 변수를 동시에 최적화하는 대신, 알고리즘은 경로 ($N$) 와 드론 ($Q$) 의 작은 부분집합을 반복적으로 선택합니다.
• 변수 선택: 부분집합은 다음과 같이 선택됩니다:
  • 변수의 수 ($|N| \times |Q|$) 는 사용 가능한 큐비트 수 ($m$) 를 초과하지 않습니다.
  • 부분집합에는 재분배를 촉진하기 위해 가장 높은 완료 시간 (병목) 을 가진 드론과 가장 낮은 완료 시간 (과부하되지 않음) 을 가진 드론이 포함됩니다.
  • 선택은 각 선택된 드론에 현재 적어도 하나의 경로가 할당되어 있도록 하여 자명하지 않은 해를 보장합니다.
• 양자 서브루틴: 선택된 부분 문제는 단일 레이어의 $R_y$ 회전과 선형 $CZ$ 얽힘을 갖는 **하드웨어 효율적 안사츠 (ansatz)**를 사용하는 **변분 양자 고유값 솔버 (VQE)**로 해결됩니다.
• 반복: 선택되지 않은 변수는 고정되며, 수렴할 때까지 이 과정이 반복됩니다.

C. 하드웨어 효율적 안사츠

본 논문은 $CZ$얽힘 게이트의 선형 체인으로 분리된 두 개의$R_y$ 회전 블록으로 구성된 특정 VQE 안사츠를 사용합니다. 이 설계는 NISQ 장치와의 호환성과 QAOA 와 관련된 깊은 회로 및 높은 계산 비용을 피하면서 단일 레이어로 고품질 해를 생성할 수 있는 능력 때문에 선택되었습니다.

3. 주요 기여

1. 새로운 알고리즘: 현재 양자 하드웨어로 해결 가능한 관리 가능한 부분 문제로 고복잡도 드론 스케줄링을 분해하는 하이브리드 접근법인 QUACOD 의 도입.
2. 확장성: 좌표 하강이 이론적 양자 우위와 실용적 NISQ 제한 사이의 간극을 메울 수 있음을 입증하여, 이전 방법들이 처리했던 것보다 훨씬 큰 문제의 해결을 가능하게 함.
3. 성능 검증: 해의 품질 (더 낮은 완료 시간) 과 확장성 모두에서 QUACOD 가 최첨단 (QUADRO) 보다 우수함을 보여주는 경험적 증거.
4. 하드웨어 효율성: 하드웨어 효율적 회로가 조합 최적화에 효과적임을 검증하여 근미래 양자 배포의 실현 가능성을 지지함.

4. 실험 결과

저자들은 두 가지 데이터셋에 대해 양자 하드웨어 (Qiskit) 의 고전적 시뮬레이션을 사용하여 QUACOD 를 평가했습니다:

• QUADRO 와의 비교 (Augerat 데이터셋):

  • QUACOD 는 드론 수와 경로 수가 다양한 6 개의 사례에서 테스트되었습니다.
  • 결과: QUACOD 는 QUADRO 의 하이브리드 및 순수 양자 접근법 모두보다 낮은 최대 완료 시간을 가진 해를 일관되게 찾았습니다.
  • 확장성: QUADRO 는 11 대 이상의 드론이 있는 사례를 스케줄링하지 못했던 반면, QUACOD 는 최대 50 대의 드론과 1,000 개의 경로를 가진 사례를 성공적으로 처리했습니다 (QUADRO 의 한계 대비 드론은 5 배, 경로는 35 배 더 많음).

• 대규모 벤치마크 (병렬 머신 스케줄링 데이터셋):

  • 200 에서 3,000 개의 경로와 5 에서 100 개의 드론에 이르는 사례에서 실험이 수행되었습니다.
  • QUACOD 는 양자 시뮬레이션을 위해 20 개의 큐비트만 사용하여 대부분의 대규모 사례를 성공적으로 해결했습니다.
  • 한계: 두 개의 가장 큰 사례 (3,000 개의 경로, 100 대의 드론) 는 QUBO 목적 함수의 $O(n^2q^2)$항을 저장하는 데 필요한 고전적 메모리 (RAM) 제약으로 인해 실패했으며, 양자 하드웨어의 한계 때문은 아니었습니다.

5. 중요성 및 주장

본 논문은 QUACOD 가 다음과 같은 이유로 NISQ 시대의 실용적 양자 응용을 향한 중요한 걸음이라고 주장합니다:

• 자원 장벽 극복: 고전적 분해 전략 (좌표 하강) 을 활용하여 제한된 큐비트로도 복잡한 물류 문제를 해결할 수 있음을 입증함.
• 실용적 적용 가능성: 기존 양자 프레임워크보다 우수한 확장성을 달성하여, 드론 부대 규모가 큰 실제 세계 드론 부대 관리에 실현 가능한 후보가 됨.
• 하드웨어 정렬: 하드웨어 효율적 안사츠를 활용함으로써 현재 및 근미래 양자 장치의 능력과 부합함.

인정된 한계

저자들은 겸손하게 다음과 같은 몇 가지 한계를 지적합니다:

• 이론적 격차: 사용된 특정 좌표 하강 구현의 수렴 속도나 수렴 보장에 대한 공식적인 이론적 증명은 없습니다.
• VQE 이론: 이러한 유형의 최적화 문제에 대해 VQE 가 고전적 방법보다 우월하다는 것을 뒷받침하는 이론적 증명은 없으며, 결과는 경험적입니다.
• 모델 단순화: 드론 스케줄링 모델은 동일한 드론과 미리 계산된 경로를 가정하여, 이질적인 부대와 동적 라우팅을 포함할 수 있는 실제 세계 물류 시스템의 복잡성을 단순화했습니다.