⚛️ 양자물리학

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

이 논문은 추가적인 큐비트 없이 서브투어 제약 조건을 최적화 과정에 직접 통합하고, 바렌 플래토(barren plateau) 현상을 완화하며 조건이 좋지 않은 지형에서의 수렴을 개선하기 위해 스마트한 파라미터 초기화 전략을 채택한 차량 경로 문제(Vehicle Routing Problem)를 위한 새로운 양자 근사 최적화 알고리즘(QAOA) 접근 방식을 제안한다.

원저자: Emanuele Casciaro, Mario De Simone, Stefano Martina, Fabio Mascherpa, Alfonso Amendola, Filippo Caruso

게시일 2026-11-02

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Emanuele Casciaro, Mario De Simone, Stefano Martina, Fabio Mascherpa, Alfonso Amendola, Filippo Caruso

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

배송 트럭들이 중앙 창고에서 출발하여 수십 곳의 장소를 방문해야 하며, 교통 체증을 피하고 모든 지점을 방문하지 않은 채 경로가 다시 되돌아오는 일이 없도록 해야 하는 한 도시를 상상해 보십시오. 이것은 현대 공급망의 핵심에 자리 잡고 있는 고전적인 과제인 차량 경로 문제(Vehicle Routing Problem)입니다. 이 경로들을 조직하는 단 하나의 최선책을 찾는 것은 전통적인 컴퓨터에게 매우 어려운 일인데, 가능한 조합의 수가 너무 빠르게 증가하여 가장 강력한 기계조차 그 모든 것을 확인하려다 길을 잃기 때문입니다. 이를 해결하기 위해 과학자들은 양자 역학의 기묘한 법칙을 사용하는 새로운 종류의 컴퓨팅으로 눈을 돌리고 있습니다. 이 양자 기계들은 선택지를 하나씩 확인하는 것이 아니라, 한 번에 많은 가능성을 탐색할 수 있어 선택의 미로를 통과하는 잠재적인 지름길을 제공합니다. 그러나 이 기계들에게 정답을 찾는 법을 가르치는 것은 마치 짙은 안개 속에서 배를 인도하는 것과 같습니다. 명확한 시작점이 없으면 컴퓨터는 어떤 방향이 최선의 해답으로 이어지는지 알 수 없는 광활하고 평탄한 지형 속에서 길을 잃기 쉽습니다.

피렌체 대학교와 Eni S.p.A.의 연구진은 특히 차량 경로 문제를 위해 이러한 양자 컴퓨터를 안개 속에서 안내하는 새로운 방법을 개발했습니다. 그들의 연구는 오늘날 사용 가능한 디지털 양자 컴퓨터에서 실행되도록 설계된 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm)이라는 방법에 초점을 맞추고 있습니다. 연구진은 이러한 기계들이 실제 세계의 경로 작업을 해결하는 것을 방해하는 두 가지 주요 장애물을 식별했습니다. 첫째, 알고리즘이 종종 무작위 설정으로 시작되어 막다른 골목에 다다르는데, 이는 컴퓨터가 어떻게 답을 개선할지 학습할 수 없는 현상인 '배리언 플레이토(barren plateau, 불모지)'라고 알려져 있습니다. 둘째, 트럭이 몇몇 지점 주변을 비효율적으로 뱅뱅 도는 것을 방지하는 수학적 규칙은 매우 복잡하여 보통 추가적인 메모리 공간을 요구하는데, 초기 단계의 양자 칩에는 그만한 공간이 충분하지 않습니다.

첫 번째 장애물을 극 overcome 하기 위해, 연구팀은 알고와리즘의 시작 조건을 설정하는 스마트한 방법을 만들었습니다. 무작위로 추측하는 대신, 그들은 가장 낮은 에너지 상태(최선의 경로에 해당함)를 주는 특정 구조화된 시작점들을 테스트했습니다. 이 접근 방식은 훈련이 시작되기도 전에 컴퓨터가 나아가야 할 방향을 가리키는 나침반 역할을 합니다. 이렇게 함으로써, 그들은 방문 지점의 수가 증가하더라도 기계가 정답에 훨씬 더 잘 수렴한다는 것을 발견했습니다. 이 방법은 도시 지도의 구체적인 세부 사항을 미리 알 필요 없이 작동하므로, 다양한 경로 시나리오에 대해 신뢰할 수 있는 도구가 됩니다.

두 번째 돌파구는 컴퓨터가 루프(순환) 방지 규칙을 처리하는 방식과 관련이 있습니다. 과거에는 알고리즘이 이러한 루프를 피하도록 강제하기 위해 양자 프로세서의 귀중한 공간을 차지하는 추가 변수들을 더해야 했습니다. 연구진은 추가 변수 없이도 제약 조건을 근사적으로 처리하는 수학적 트릭을 사용하여 이 규칙을 계산에 직접 내장하는 방법을 찾아냈습니다. 이를 통해 양자 컴퓨터는 더 적은 자원을 사용하면서도 규칙을 이해하고 강제할 수 있습니다. 이 효율적인 인코딩과 스마트한 시작 전략을 결과적으로 결합함으로써, 연구팀은 알고리즘이 3개, 4개, 5개의 위치를 가진 작은 네트워크에 대해 올려 정답 경로를 성공적으로 찾아낼 수 있음을 입증했습니다. 시뮬레이션에서 컴퓨터는 잘못된 루프 속에서 길을 잃는 대신, 정답에 확률을 집중시키며 일관되게 최적의 경로를 식별해 냈습니다.

이 연구는 적절한 준비가 뒷받침된다면 양자 컴퓨터가 기존의 시도들보다 더 효과적으로 이러한 복잡한 물류 문제를 다룰 수 있음을 확인시켜 줍니다. 연구진은 그들의 방법이 서로 다른 차량 수와 목적지 수에 걸쳐 작동하며, 테스트에서 매우 높은 성공률을 달anim했음을 보여주었습니다. 현재의 실험은 시뮬레이터에서 수행되었으며 기존 하드웨어의 제약으로 인해 작은 네트워크로 제한되었지만, 이 접근 방식은 추가 메모리 없이도 어려운 루프 방지 규칙을 포함한 전체 경로 문제를 해결하는 것이 가능하다는 것을 증명합니다. 이 작업은 양자 기술이 성숙해짐에 따라 연료 비용을 절감하고 효율성을 높일 수 있는, 배송 시스템을 최적화하기 위한 양자 기술 활용의 길을 제시합니다. 연구 결과는 제약 조건을 코드에 작성하는 방식에 대한 세심한 엔지니어링이 하드웨어 자체만큼이나 중요하다는 것을 나타내며, 물류 및 그 외 분야의 미래 적용을 위한 실질적인 청사진을 제공합니다.

기술 요약: 스마트 초기화 및 서브투어 인코딩을 적용한 양자 차량 경로 문제(Quantum Vehicle Routing Problem)

문제 정의
차량 경로 문제(Vehicle Routing Problem, VRP)는 중앙 데포(depot)에서 출발하여 일련의 목적지들을 방문하고 다시 돌아오는 차량 함대의 최적 경로를 결정하는 조합 최적화 과제이다. 이 문제는 NP-Hard에 해당하며, 정확한 고전적 해법을 위해서는 지수 함수적인 연산이 필요하기 때문에 대규모 인스턴스에 대한 정밀 솔버의 확장성을 제한한다. 휴리스틱 방법들이 존재하지만, 종종 최적이 아닌 결과를 낸다. 본 논문은 디지털 양자 장치에서 QAOA(Quantum Approximate Optimization Algorithm)를 사용하여 VRP를 해결하는 데 초점을 맞춘다. VRP를 양자 솔버에 인코딩할 때 발생하는 특정 과제는 "서브투어 제거(subtour elimination)" 제약 조건(식 1f)으로, 이는 데포를 포함하지 않는 폐쇄 회로(closed cycles)를 방지한다. 전통적인 QUBO(Quadratic Unconstrained Binary Optimization) 정식화는 이러한 제약 조건을 제외하거나, 이를 강제하기 위해 지수적으로 많은 추가 이진 슬랙 변수(slack variables)를 요구하여 큐비트 요구량을 과도하게 늘리고 복잡한 사후 처리를 유발한다.

방법론
저자들은 두 가지 주요 병목 현상인 '악조건의 지형에서의 불량한 파라미터 초기화'와 '부등식 제약 조건에 필요한 높은 큐비트 오버헤드'를 해결하는 QAOA 기반 프레임워크를 제 제안한다.

스마트 초기화 전략 (Smart Initialization Strategy):
변분 학습을 방해하는 '바렌 플래토(barren plateau)' 현상(시스템 크기에 따라 기울기가 지수적으로 사라지는 현상)을 완화하기 위해, 저자들은 결정론적 초기화 전략을 도입한다. 무작위 파라미터 선택 대신, 특정 파라미터 공간의 부분 집합에 대해 그리드 탐색을 수행한다. 이들은 $\alpha_d = d\pi/D$ 인 $\gamma_k = \beta_k = \alpha_d$ 인 구성에 대해 기대 에너지 $\langle\psi(\gamma, \beta)| H_C |\psi(\gamma, \beta)\rangle$ 를 평가한다. 가장 낮은 에너지를 생성하는 구성을 클래식 최적화 도구의 시작점으로 선택한다. 이 접근 방식은 훈련을 기울기가 소멸하는 영역이 아닌 낮은 에너지 상태 근처에서 시작하는 것을 목표로 한다.
슬랙 변수 없는 서브투어 제약 조건 인코딩 (Subtour Constraint Encoding without Slack Variables):
Montañez-Barrera 등(2024)의 연구를 바탕으로, 저자들은 추가 큐비트를 도입하지 않고 서브투어 제거 제약 조건을 QUBO 해밀토니안에 직접 통합한다. 이들은 지수 함수의 2차 테일러 전개를 사용하여 부등식 제약 조건을 근사한다. 구체적으로, 부등식 제약 $h_S(x) \geq 0$ 은 $e^{-h(x)} \approx e - e \cdot h(x) + \frac{e}{2}h(x)^2$ 근사를 사용하여 완화된 최적화 문제로 변환된다. 그 결과, 표준 라그랑주 승수 $\lambda$ 와 함께 서브투어 제약에 대한 선형 및 이차 항을 포함하는 수정된 QUBO 목적 함수가 생성되며, 이는 하이퍼파라미터 $\lambda_1$ 및 $\lambda_2$ 에 의해 제어된다.

주요 기여

새로운 초기화: 무작위 초기화 시 발생하는 바렌 플래토의 영향을 제한하고 수렴 확률을 개선하는 파라미터 초기화 전략을 제시하였으며, 이는 큐비트 수가 증가함에 따라 효과적임이 입증되었다.
직접적인 서브투어 통합: 서브투어 제거 제약을 QAOA 최적화 루프에 직접 인코딩하는 방법을 제공한다. 이는 추가적인 슬랙 변수나 지수적인 큐비트 수 증가 없이도 구현이 가능하게 하여, "엔드 투 엔드(end-to-end)" 양자 솔루션을 가능케 한다.
하이퍼파라미터 튜닝: Optuna를 사용하여 QUBO 인코딩을 형성하는 최적의 하이퍼파라미터 구성( $\lambda, \lambda_1, \lambda_2$ )을 식별함으로써, 해밀토니안의 바닥 상태(ground state)가 최적의 실행 가능한 해에 대응하도록 보장한다.

결과
저자들은 노이즈가 없는 시뮬레이터에서 노드 수 $N$ 이 3에서 5 사이이고 차량 수 $K$ 가 다양한 VRP 인스턴스를 통해 접근 방식을 검증하였다.

초기화 성능: 무작위 초기화와의 비교를 통해, 스마트 초기화 전략은 다양한 문제 클래스에 걸쳐 일관된 성공 확률을 유지하는 반면, 무작운 초기화는 $N$ 이 증가함에 따라 바렌 플래토로 인해 성능이 크게 저하됨을 보여주었다.
제약 조건 충족: 제안된 인코딩은 높은 확률로 $N=5$ 까지의 인스턴스를 성공적으로 해결했다. $N=3$ 의 경우, 서브투어 제약은 다른 제약 조건에 의해 자연스럽게 충족되지만 인코딩은 여전히 유효하다. $N=4$ 및 $N=5$ 의 경우, QAOA 출력 확률이 이론적으로 올바른 해에 날카롭게 집중되어, 실행 불가능하거나 차선책인 구성으로부터 최적 경로를 효과적으로 분리해 냈다.
큐비트 효율성: 제안된 인코딩은 부등식 제약에 필요한 변수의 지수적 증가를 피함으로써, 표준 슬랙 변수 정식화와 비교했을 때 필요한 큐비트 레지스터 크기를 $O(2^N)$ 만큼 줄인다.

의의 및 주장
본 논문은 VRP 맥락에서 QAOA 파라미터에 대한 효과적이고 문제 크기에 독립적인 초기화를 달성한 첫 번째 사례라고 주장한다. 또한, 보조 큐비트나 클래식 사후 처리 없이 서브투어 부등식을 QAOA 최적화 루틴에 직접 인코딩한 첫 번째 사례임을 명시한다.

저자들은 이러한 기여가 양자 기반 솔루션을 사용하여 VRP 인스턴스를 효과적으로 해결하는 길을 열어준다고 위치시킨다. 이들은 공간 효율적인 문제 인코딩과 개선된 초기화를 활용함으로써, 특히 결함 허용(fault-tolerant) 양자 컴퓨터가 가용해짐에 따라 양자 최적화가 클래식 경로 탐색 방법의 유효한 대안 또는 보완책이 될 수 있다고 주장한다. 다만, 저자들은 현재의 한계에 대해 겸허한 태도를 유지한다. 실험은 노이즈가 없는 시뮬레이터 상의 작은 인스턴스( $N \leq 5$ )로 제한되었으며, QUBO로의 변환은 여전히 하이퍼파라미터 선택에 매우 민감하여 검색 과정이 필요하다. 저자들은 향ap후 연구가 접근 방식을 더욱 간소화하기 위해 문제의 불변량(예: $N$ 과 $K$ 의 함수)에 기반한 일반적인 하이퍼파라미터 구성을 결정하는 데 집중해야 한다고 제언한다.

유사한 논문