⚛️ 양자물리학

Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

이 논문은 정확한 그래디언트 CVaR 및 베이신 호핑 재시작(basin-hopping restarts)을 통해 훈련된 변분 양자 콜모고로프-아놀드 네트워크가 단 $\lceil \log_2 (N-1)! \rceil$ 개의 큐비트만을 사용하여 시간 의존적 그래프에서의 외판원 문제를 해결할 수 있음을 입증하며, 전통적인 원-핫 인코딩에 비해 큐비트 요구 사항을 크게 줄이면서도 최대 10개 지점에 대해 최적의 해를 달성한다.

원저자: Hikaru Wakaura

게시일 2026-10-15

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Hikaru Wakaura

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

배달 기사가 모든 도시를 정확히 한 번씩 방문하고 다시 집으로 돌아와야 하는 상황을 상상해 보십시오. 이때 가능한 한 짧은 거리를 이동하는 것이 목표입니다. 이것이 바로 물류, 스케줄링, 회로 설계의 핵심에 자리 잡고 있는 고전적인 퍼즐인 '외판원 문제(Traveling Salesman Problem)'입니다. 몇 개의 도시에 대해 완벽한 경로를 찾는 것은 쉽지만, 도시 목록이 늘어날수록 난이도는 폭발적으로 증가합니다. 새로운 도시가 추가될 때마다 가능한 경로의 수가 너무 빠르게 곱절로 늘어나기 때문에, 가장 빠른 슈퍼컴퓨터조차 최적의 경로를 찾으려다 길을 잃을 수 있습니다. 수십 년 동안 과학자들은 이러한 퍼즐을 더 빠르게 해결하기 위해 양자 역학의 법칙을 이용해 정보를 처리하는 기계인 양자 컴퓨터에 주목해 왔습니다. 그러나 큰 장애물이 남아 있었습니다. 바로 계산 과정이 오류와 불필요한 복잡함 속에 빠지지 않도록 문제를 양자 컴퓨터가 이해할 수 있는 언어로 어떻게 번역하느냐 하는 문제였습니다.

QuantScape Inc.의 한 연구원은 양자 컴퓨터가 미로를 통과하도록 안내하는 새로운 방법을 시연했으며, 최대 10개의 도시가 포함된 지도에서 최단 경로를 찾는 데 성공했습니다. 물리적인 기계가 아닌 양자 하드웨어 시뮬레이션에 의존한 이 연구는 이전 방식보다 훨씬 적은 수의 양자 비트(양자 컴퓨터의 기본 정보 단위)를 사용하는 방법을 도입했습니다. 더 중요한 점은, 하나의 지침 세트가 교통 체증처럼 하루 중 변하는 도로 상황에 적응할 수 있으며, 매번 새로운 시나리오마다 다시 학습할 필요가 없다는 것을 보여주었다는 것입니다. 이 결과는 적절한 인코딩과 학습 기술이 뒷받인다면, 하드웨어가 계속 개선되는 조건 하에 양자 컴퓨터가 곧 현재는 손이 닿지 않는 최적화 문제들을 다룰 수 있음을 시사합니다.

핵리적인 과제는 문제를 기계가 이해할 수 있도록 어떻게 기록하느냐에 달려 있습니다. 전통적인 방식은 도시의 각 조합과 경로상의 각 위치마다 별도의 양자 비트를 할당합니다. 10개의 도시가 있는 지도의 경우, 이 방식은 81개의 비트를 필요로 하며, 컴퓨터가 유효하지 않은 경로를 끊임없이 확인하고 폐기하게 만들어 시간과 에너지를 낭비하게 만듭니다. 새로운 연구는 '레머 코드(Lehmer code)'라고 불리는 수학적 체계에서 영감을 얻은 다른 전략을 사용하는데, 이는 본질적으로 모든 가능한 경로를 목록의 순서에 따라 순위를 매기는 방식입니다. 이 방법은 10개 도시를 위해 단 19개의 비트만을 필요로 하여 획기적인 감소를 보여줍니다. 이 압축된 코드를 사용함으로써 양자 컴퓨터의 모든 상태는 유효한 경로를 나타내게 되며, 페널티 체크를 위한 과정이 필요 없어집니다. 탐색을 효율적으로 만들기 위해, 연구진은 코드의 비트 하나를 뒤집는 것이 경로의 작은 논리적 변화에 대응하도록 상태를 배치하여 컴퓨터가 솔루션 공간을 부드럽게 탐색할 수 있도록 했습니다.

양자 컴퓨터를 안내하기 위해 연구진은 '변분 양자 콜모고로프-아르노프 네트워크(variational quantum Kolmogorov–Arnold network)'라는 하이브리드 시스템을 채택했습니다. 이것을 지도를 관찰하고 시간대를 파악한 뒤, 양자 회로의 다이얼을 적절한 위치로 설정하는 스마트 컨트롤러라고 생각하면 됩니다. 이 컨트롤러는 특정 지도마다 설정을 하드코딩하는 대신, 도시 간의 거리와 현재 시간에 따라 회로를 조정하는 일반적인 규칙을 학습합니다. 이를 통해 전력망이나 출퇴근 시간대의 도로 네트워크처럼 이동 시간이 변하는 '시간 의존적 그래프'를 처리할 수 있습니다. 이 컨트롤러는 긴 경로를 선택할 위험을 최소로 줄이는 것을 목표로 학습되었습니다. 단순히 평균 길이를 찾는 것이 아니라, 발생 가능한 상위 몇 퍼센트의 결과 내에서 최악의 시나리오에 초점을 맞춤으로써 최종 결과가 견고하고 신뢰할 수 있도록 했습니다.

학습 과정 자체도 엄격하게 설계되었습니다. 이는 컴퓨터가 최선의 답 대신 '적당히 좋은' 답에 안주해 버리는 '지역 최솟값(local minimum)'의 함정에 빠지는 것을 피하기 위함입니다. 연구진은 넓은 탐색에서 시작하여 점차 초점을 좁혀가는 다단계 전략을 사용했으며, 막다른 골목에서 벗어날 수 있도록 설정을 의도적으로 흔드는 기술을 결в합했습니다. 또한, 시스템이 탐색 지형의 얕은 골짜기에서 뛰어오를 수 있도록 돕는 '베이슨 호핑(basin hopping)'이라는 기법을 사용했습니다. 대칭적인 형태와 무작위의 불규로한 네트워크를 모두 포함한 4개에서 10개의 도시 지도로 테스트했을 때, 이 접근 방식은 작은 규모의 지도에서는 모든 경우에서 완벽한 경로를 찾아냈습니다. 훨씬 더 어려운 10개 도시 지도의 경우, 이 방법은 120번의 시도 중 112번에서 최적의 경로를 찾아냈으며, 나머지 실패 사례들도 완벽한 거리와 단 1% 차이밖에 나지 않았습니다.

결정적으로, 이 연구는 유망해 보였던 몇 가지 대안적인 아이디어들을 검증하여 배제했습니다. 연구진은 운전자의 위치를 단계별로 추적하기 위해 각 도시당 하나씩 총 10개의 비트를 사용하는 더 단순한 접근 방식을 테스트했습니다. 하지만 이 방식은 연속적인 정거장 사이의 복잡한 관계를 표현할 수 없었기 때문에 6개 이상의 도시가 있는 지도에서는 완전히 실패했습니다. 또한, 두 구간을 교체하여 경로를 개선하는 '2-opt'라는 표준 고전 알고리즘과도 비교했습니다. 2-opt는 효과적이긴 하지만, 양자 회로는 훨씬 더 나은 시작점을 제공했으며, 두 방법을 결합했을 때 각각의 방법보다 뛰어난 성능을 보였습니다. 이 연구는 성공의 원인이 단순히 양자 회로의 힘 때문이 아니라, 문제를 인코딩하는 특정한 방식과 컨트롤러의 정교한 학습에 있음을 확인시켜 주었습니다.

또한, 이 연구는 측정의 효율성 측면에서도 주목할 만한 성과를 보여주었습니다. 실제 양자 컴퓨터에서 답을 읽으려면 명확한 신호를 얻기 위해 프로세스를 여러 번 반복해야 합니다. 시뮬레이션 결과, 단 100번의 읽기만으로도 시스템이 최적의 경로를 안정적으로 식별할 수 있음을 보여주었습니다. 이는 충분한 비트를 갖춘 물리적 양자 컴퓨터가 가용해졌을 때, 이 방법이 수백만 번의 반복 없이도 결과를 빠르게 전달할 수 있음을 시사합니다. 연구진은 현재 작업이 양자 행동을 시뮬레이션하는 클래식 컴퓨터에서 수행되었지만, 이 기술들이 실제 하드웨어에서도 작동하도록 설계되었다는 점을 언급했습니다. 다음 단계는 실제 기계의 노이즈가 있는 환경에서 시스템을 테스트하고, 수동으로 확인하기에는 가능한 경로의 수가 너무 방대한 더 큰 규모의 지도로 확장하는 것입니다.

이 연구는 양자 최적화를 실용적으로 만드는 데 있어 중요한 진전입니다. 인코딩 문제를 해결하고 다양한 지도와 시간에 걸쳐 일반화될 수 있는 컨트롤러를 구축함으로써, 연구진은 복잡한 경로 문제를 효율적으로 해결할 수 있는 길을 제시했습니다. 하나의 파라미터 세트로 시간 의존적 변화를 처리할 수 있는 능력은 상황이 결코 정적이지 않은 현실 세계의 응용 분야에서 특히 유망합니다. 완전한 기능을 갖춘 양자 최적화 도구로 가는 여정은 계속되고 있지만, 이 연구는 이러한 기계들이 복잡한 세상 속에서 최단 경로를 찾도록 훈련하는 방법에 대한 명확한 청사진을 제공합니다.

기술 요약: Lehmer-Code VQKAN을 이용한 TSP 해결

문제 정의
외판원 문제(Traveling Salesman Problem, TSP)는 근본적인 NP-난해(NP-hard) 조합 최적화 문제이다. 정밀한 고전적 방법들은 지수적으로 확장되는 반면, 변분 양자 알고리즘(Variational Quantum Algorithms, VQAs)은 노이로성 중간 규모 양자(NISQ) 장치를 위한 잠재적 경로를 제공한다. 그러나 표준적인 TSP 양자 인코딩은 다음과 같은 중대한 장애물에 직면한다:

원-핫 인코딩(One-hot encoding): $N$ 개의 지점에 대해 $(N-1)^2$ 개의 큐비트가 필요하다. 대부분의 기저 상태는 유효한 투어(tour)가 아니므로, 비용 경관(cost landscape)을 지배하고 튜닝하기 어려운 페널티 항이 필요하다.
이진 인코딩(Binary encoding): 큐비트 수를 $(N-1)\lceil \log_2 N \rceil$ 로 줄여주지만, 여전히 페널티나 복구가 필요한 유효하지 않은 문자열을 남긴다.
순열 인코딩(Permutation encoding, Lehmer code): 투어를 $(N-1)!$ 개의 순열 중 그 순위(rank)로 라벨링하며, 단 $n = \lceil \log_2(N-1)! \rceil$ 개의 큐비트만을 필요로 한다. 결정적으로, 모든 기저 상태가 유효한 투어에 대응하므로 페널티 항이 필요 없다. 그러나 이 인코딩을 사용하는 기존의 변분 솔버들은 랭크 경관의 국소성(locality) 부족과 성공률 저하로 인해 6개 지점 이상으로 확장하는 데 어려움을 겪어왔다.

방법론
저자는 압축된 Lehmer-code 인코딩과 변분 양자 콜모고로프-아르노프 네트워크(Variational Quantum Kolmogorov–Arnold Network, VQKAN), 그리고 특화된 훈련 체계를 결합한 파이프라인을 제안한다.

인코딩 및 판독(Read-out):
- 투어는 $n = \lceil \log_2(N-1)! \rceil$ 큐비트에 저장된 Lehmer 코드로 표현된다.
- 랭크 경관의 비국소성 문제를 해결하기 위해, 큐비트로부터 읽어들인 정수는 **이진 반사 그레이 코드(binary-reflected Gray code)**로 해석된다. 이를 통해 1비트 차이가 나는 상태들이 연속적인 Lehmer 코드로 이어지게 하며, 이는 마지막 방문 지점의 순서만 바뀜을 의미한다.
- 회로는 단일 큐비트 $R_y$ 회전과 인접 이웃 $CZ$ 게이트로 구성된 얕은 하드웨어 효율적 안사츠(ansatz, 깊이 $d=2$ )이다.
VQKAN 각도 생성:
- 각 인스턴스마다 회전 각도를 직접 최적화하는 대신, 회전 각도는 VQKAN에 의해 생성된다.
- 각 각도는 입력 특징량인 시간 $t$ 와 거리 행렬 $D$ 의 특징량(구체적으로, $D$ 의 행 평균을 최대값으로 정규화한 값)에 대한 학습 가능한 이차 스플라인(quadratic spline)이다.
- 이를 통해 단일 파라미터 세트로 (교통량이나 전력망 경로 변경과 같이) 시간이 지남에 따라 거리가 변하는 일련의 그래프들을 처리할 수 있어, 인스턴스마다 재학습할 필요가 없다.
손실 함수 및 훈련:
- 회로는 투어 길이에 대한 **조건부 가치 위험(Conditional Value at Risk, CVaR)**을 최소화하도록 훈련된다. CVaR는 확률 질량을 가장 짧은 투어에 집중시키며, 이는 "최선-중-최고(best-of-shots)" 판독 전략과 일치한다.
- 그래디언트는 **아드조인트 방법(adjoint method)**을 사용하여 정확하게 계산된다 (회로가 실수 진폭을 사용하므로 가능하다).
- 옵티마이저는 CVaR 경관을 탐색하고 지역 최솟값에 빠지는 것을 피하기 위해 네 가지 특정 전략을 채택한다:
  - 멀티 스타트(Multi-start): 서로 다른 무작위 시드에서 시작하는 다수의 독립적인 실행.
  - 리스크 레벨 스케줄(Risk-level schedule): $\alpha=0.5$ 에서 시작하여 $\alpha=0.02$ 로 감소하는 커리큘럼 학습 방식으로, 초기에는 경관을 부드럽게 만들고 나중에는 최적점에 집중한다.
  - 작은 각도 초기화(Small-angle initialization): 배런 플래토(barren plateaus)를 피하기 위해 파라미터를 항등 근처에서 초기화한다.
  - 베이신 호핑 재시작(Basin-hopping restarts): 수렴 후, 파라미터를 섭동시켜 잔여 지역 최솟값에서 탈출한다.
판독 및 후처리:
- 상태를 $M$ 번 샘플링한다 (예: $10^2$ ~ $10^5$ 샷). 가장 짧은 샘플링된 투어를 반환한다.
- 선택적 클래식 후처리로 상위 20개 샘플 투어에 2-opt를 적용하여 솔루션을 정밀화한다.

주요 결과
본 방법은 대칭 다각형 및 비대칭 무작위 그래프에 대해 $N=4, 6, 8, 10$ 에서 평가되었다.

성공률: 전체 옵티마이저(모든 훈련 전략 포함)는 세 번의 실행 프로토콜에서 $N=4$ 부터 $10 $까지의 경우에 대해 **100%의 사례**(36/36 트리플)에서 최적의 투어를 반환했다. 더 엄격한 30회 반복 실험($ N=10$)에서는 120건 중 112건(93.3%)에서 최적해를 찾았으며, 나머지 실패 사례들도 최적 길이에 1% 이내로 근접했다.
큐비트 효율성: $N=10$ 일 때, 이 방법은 원-핫 인코딩의 81개 큐비트에 비해 19개의 큐비트만을 사용한다.
측정 효율성: 최적의 투어는 단 $10^2$ 회의 측정 샷만으로도 발견되었다. $N=10$ 에서 최적해를 찾지 못한 것은 샘플링 노이즈가 아니라 상태 벡터 자체에 최적 투어가 포함되지 않았기 때문(훈련의 한계)이었다.
일반화: 시간 의존적 그래프에서, 거리 특징량과 시간에 대해서만 훈련된 네트워크는 보지 못한 시간대에서도 성공적으로 일반화했으나, 시간만으로 훈련된 네트워크는 효과적인 보간에 실패했다.
절제 연구(Ablation Studies):
- **베이신 호핑(Basin hopping)**이 $N=10$ 에서 잔여 지역 최솟값을 제거하는 핵심 요소임을 확인했다.
- 더 깊은 회로(깊이 4)는 깊이 2 회로보다 성능을 개선하지 못했으며 훨씬 더 많은 파라미터를 요구했다.
- 그레이 코드 판독과 거리 특징량은 높은 성공률과 일반화를 위해 필수적이었다.
- 클래식 제어: " $N$ -큐비트 원-핫 워크"(N개의 큐비트를 사용하여 판매자가 단계별로 이동함)는 $N \ge 6$ 에서 유효한 투어를 찾는 데 실패하여, $N$ 개의 큐비트가 투어의 분포를 나타내기에 불충분함을 확인했다. 훈련된 회로는 무작위 투어에서 시작된 2-opt보다 더 나은 초기 솔루션을 제공했다.

의의 및 주장
본 논문은 이전에 6개 지점 이상에서 실패했던 순열 인코딩 기반 VQA의 최적화 병목 현상을 해결한다고 주장한다. VQKAN을 통해 큐비트 효율적인 Lehmer code를 결합함으로써, 저자는 다음을 입증한다:

확장성: 표준 인코딩보다 훨씬 적은 큐비트를 사용하여 $N=10$ 까지의 TSP 인스턴스를 안정적으로 해결한다.
일반화: 단일 파라미터 세트로 시간 의당 그래프를 처리할 수 있어, 인스턴스별 재학습을 피할 수 있다.
최적화 전략: 순열 랭크의 비국소적 경관을 극복하기 위해 특정 옵티마이저 구성 요소(베이신 호핑, 리스크 레벨 스케줄링)가 필수적임을 확인했다.

저자는 본 시뮬레이션이 인코딩과 옵티마이저의 생존 가능성을 확립하지만, 아직 큰 $N$ 에 대해 최첨단 클래식 휴리스틱 대비 양자 우위를 입증한 것은 아니며, 그래디언트 추정 시의 샷 노이즈를 고려하지 않았음을 명시적으로 밝히고 있다. 이 연구는 순열 인코딩 기반 VQA를 NISQ 하드웨어에서 확장할 수 있음을 보여주는 개념 증명(proof-of-concept) 역할을 한다.

유사한 논문