큰 문제: "작은 마을"의 한계

당신이 거대한 퍼즐(연결을 최대화하기 위해 네트워크를 반으로 나누는 최적의 방법을 찾는 것)을 풀려고 한다고 상상해 보세요. 당신에게는 아주 똑똑하지만 주의 집중 시간이 매우 짧은 로봇 조수(QAOA 알고리즘)가 있습니다.

표준 버전의 이 로봇은, 만약 당신이 퍼즐의 특정 조각을 살펴보라고 요청하면, 바로 옆에 붙어 있는 조각들만 "볼" 수 있습니다. 만약 퍼즐이 작은 마을이라면, 로봇은 전체를 빠르게 볼 수 있습니다. 하지만 퍼즐이 길고 구불구불한 도로가 있는 거대하고 거대한 도시(다이어미터(diameter)가 큰 그래프)라면, 로봇은 갇혀버리고 맙니다.

설령 로봇에게 시간을 조금 더 준다 해도(회로의 "깊이(depth)"를 추가하더라도), 로봇은 불과 몇 블록 너머까지만 볼 수 있을 뿐입니다. 도시의 반대편은 볼 수 없습니다. 전체 그림을 볼 수 없기 때문에, 로로봇은 최적의 해답에 대해 잘못된 추측을 하게 됩니다. 논문에서는 이를 **"국소성 병목 현상(locality bottleneck)"**이라고 부릅니다. 로봇이 너무 국소적인 정보에만 매몰되어 있어 전역적인(global) 문제를 해결하지 못하는 것입니다.

해결책: "텔레포트 도로" 건설하기

저자들은 영리한 해결책을 제안합니다. 퍼즐 자체를 바꾸는 대신, 로봇이 이동할 때 사용하는 도로를 바꾸는 것입니다.

원래의 그래프를 로컬 도로만 있는 도시라고 생각해 보세요. 로봇이 A 집에서 B 집까지 운전해서 가야 하는데, 두 집이 멀리 떨어져 있다면 시간이 아주 오래 걸립니다. 저자들은 이렇게 말합니다. "멀리 떨어진 집들 사이에 비밀 고속도로나 텔레포트 패드를 만들자."

이것을 **"수송 증강 QAOA(Transport-Augmented QAOA)"**라고 부릅니다.

퍼즐 (비용/Cost): 원래의 지도는 그대로 둡니다. 목표도 동일합니다.
도로 (믹서/Mixer): 그래프의 먼 부분들을 연결하는 새로운 보이지 않는 "지름길" 연결을 추가합니다. 이것들은 퍼즐의 규칙의 일부가 아닙니다. 단지 로봇이 정보를 더 빠르게 전달하기 위해 사용할 수 있는 추가 차선일 뿐입니다.

로봇이 움직이는 방식: "홉(Hop)" 비유

이것이 어떻게 도움이 되는지 이해하기 위해, 로봇이 연못을 건너려는 개구리라고 상상해 보세요.

표준 QAOA: 개구리는 인접한 연잎에서 다음 연잎으로 폴짝 뛰어넘을(hop) 수만 있습니다. 넓은 연못을 건너려면 많은 번의 점프가 필요합니다. 만약 연못이 너무 넓으면, 개구리는 반대편에 도달하기 전에 에너지를 다 써버립니다(회로 깊이의 한계).
수송 증강 QAOA: 저자들은 연못을 가로지르는 "마법의 다리(지름길)"를 추가합니다. 이제 개구리는 단 한두 번의 점프로 한쪽 끝에서 다른 쪽 끝으로 건너갈 수 있습니다.

논문은 이러한 다리를 추가함으로써 로봇의 "시야"(영향을 미칠 수 있는 범위)가 즉각적으로 확장된다는 것을 수학적으로 증명합니다. 단 몇 블록 앞만 보는 대신, 갑자기 도시 전체를 "볼" 수 있게 됩니다.

"라이트콘(Lightcone)" 메타포

논문은 **"라이트콘(Lightcone, 광추)"**이라는 개념을 사용합니다. 로봇이 등대라고 상상해 보세요.

표준 설정에서 빛은 짧은 거리만 비춥니다. 도시가 그 빛보다 크다면, 가장자리들은 어둠 속에 남게 됩니다.
지름길 도로를 추가함으로써, 저자들은 효과적으로 등대의 빛줄기를 넓힙니다. 그들은 등대를 더 밝게 만드는 것이 아니라(알고리즘의 깊이를 바꾸는 것이 아님), 빛이 더 멀리 도달할 수 있도록 지형을 바꿉니다.

그들은 만약 충분한 지름길을 추가하여 "다이어미터(diameter, 어떤 두 지점 사이의 가장 긴 거리)"를 매우 작게 만든다면, 로봇이 원래 도시가 얼마나 크든 상관없이 퍼즐을 거의 완벽하게 풀 수 있다는 것을 보여줍니다.

실험 결과

저자들은 세 가지 유형의 "도시(그래프)"에서 테스트를 진행했습니다:

정규 격자(Regular Grids): 이미 작은 도시들이지만, 지름길 덕분에 완벽해졌습니다.
이분 그래프(Bipartite Graphs): 중간 크기의 도시입니다. 지름길이 없을 때는 로봇이 약 74%의 점수를 얻었습니다. 지름길을 추가하자 점수가 **97.7%**로 급증했습니다.
트리(Trees, 길고 구불구불한 경로): 이들은 매우 길고 좁은 도시와 같아서 가장 어려운 유형입니다. 지름길이 없었을 때 로봇은 고전했습니다. 하지만 지름길을 추가하여 거리를 축소하자, 로봇은 **99.97%**라는 거의 완벽한 점수를 달성했습니다.

핵심 요약

주요 발견은 로봇의 실패 원인이 지능이 부족하거나 속도가 느려서가 아니라, 지도가 로봇의 짧은 주의 집중 시간보다 너무 컸기 때문이라는 점입니다.

지도에 "수송 지름길(transport shortcuts)"을 추가함으로써, 그들은 로봇이 살아가는 세상의 유효한 크기를 줄였습니다. 이를 통해 단순하고 얕은 구조의 로봇이 이전에는 손댈 수 없었던 복잡하고 대규모인 문제들을 해결할 수 있게 되었습니다. 논문은 만약 로봇이 이동해야 하는 "거리"를 줄인다면, 솔루션의 품질은 거의 완벽해지며, 원래 문제가 얼마나 컸는지는 더 이상 중요하지 않게 된다는 것을 증명합니다.

요약하자면: 그들은 로봇을 더 똑똑하게 만든 것이 아니라, 로봇이 항해하기에 세상을 더 작게 만들었습니다.

기술 요약: QAOA에서의 국소성(Locality) 문제 해결

1. 문제 정의

양자 근사 최적화 알고리즘(QAOA)은 얕은 회로 깊이( $p$ )에서 희소하고 직경(diameter)이 큰 그래프(예: MaxCut 인스턴스)에 적용될 때, **국소성 병목 현상(locality bottleneck)**이라 불리는 근본적인 한계에 직면한다.

표준 QAOA에서 국소 비용 관측값(local cost observable)의 기댓값은 상호작용 그래프의 유계된 이웃(bounded neighborhood)에만 의존한다. 구체적으로, $p$ 개의 레이어를 거친 후, "하이젠베르크 광역(Heisenberg lightcone)"은 원래의 서포트(support)로부터 최대 $p$ 번의 그래프 홉(hop)만큼 확장된다. 결과적으로, 직경이 큰 그래프의 경우, 얕은 회로는 전역적 비용 항을 최적화하는 데 필요한 먼 부분들을 "볼 수 없다". 이는 그래프의 크기나 직경이 증가함에 따라 성능 저하를 초래하며, 얕은 깊이의 QAOA가 깊이를 크게 늘리지 않고는 최적해에 도달하는 것을 방해한다.

Phantom-QAOA와 같은 변형 모델들은 가중치가 부여된 "팬텀(phantom)" 에지를 포함하도록 비용 해밀토니안을 수정하지만, 본 논문은 비용 해밀토니안을 엄격하게 변경하지 않으면서 **믹서 상호작용 기하 구조(mixer interaction geometry)**를 수정함으로써 이 한계를 해결한다.

2. 방법론: 수송 증강 QAOA (Transport-Augmented QAOA)

저자들은 수송 증강 QAOA 프레임워크를 제안한다. 핵심 전략은 원래의 문제 그래프 $G_C = (V, E)$ 를 비용 해밀토니안( $H_C$ )으로 유지하되, 선택된 지름길 에지(shortcut edges)인 수송 그래프 $G_M = (V, E_{new})$ 상의 추가적인 결합(coupling)을 통해 믹서 해밀토니안( $H_B$ )을 보강하는 것이다.

주요 구성 요소:

비용 해밀토니안 (Cost Hamiltonian): 원래의 인스턴스에 고정되어 있음:
$H_C = \sum_{(i,j) \in E} \frac{1}{2}(1 - Z_i Z_j)$
수송 믹서 (Transport Mixer): 믹서는 선택된 지름길 에지 집합 $E_{new}$ $E_{n e w}$ 상의 2-큐비트 상호작용으로 풍부해진다. 논문은 두 가지 특정 믹서 모델을 분석한다:
1. 교환 가능한 XX 믹서 (Commuting XX Mixer): $X_i X_j$ 항을 사용한다. 모든 $X_i X_j$ 는 서로 교환 가능하므로, 이를 통해 서포트 확장에 대한 정확한 대수적 분석이 가능하다.
2. 스케줄링된 XX + YY 믹서 (Scheduled XX + YY Mixer): $X_i X_j + Y_i Y_j$ 항을 사용하며, 이는 여기 호핑(excitation hopping, XY/iSWAP 하드웨어의 고유 특성)에 해당한다. 인접한 에지들이 서로 교환되지 않기 때문에, 저자들은 정확한 라이트콘(lightcone) 경계를 도출하기 위해 스케줄링된 에지 색상 회로(scheduled edge-color circuit)(에지를 매칭 $M_1, \dots, M_q$ 로 분할)를 구현한다.

이론적 프레임워크: 라이트콘 및 서포트 성장

본 논문은 전체 상호작용 그래프 $G_{int} = (V, E \cup E_{new})$ 를 기반으로 엄격한 유한 깊이 국소성 명제를 확립한다.

서포트 재귀 (Support Recursion): 초기 서포트가 집합 $S$ $S$ 인 로컬 연산자의 경우, $p$ $p$ 레이어 이후의 서포트는 반복적인 성장 영역 내에 포함된다.
- 교환 가능한 XX 믹서의 경우, 서포트는 레이어당 최대 2 홉(1번의 믹서 홉 + 1번의 비용 홉)만큼 성장하며, $G_{int}$ 내에서 $2p$ -이웃에 의해 제한된다.
- $q$ 개의 매칭 서브레이어를 가진 스케줄링된 XX + YY 믹서의 경우, 경계는 $(q+1)p$ 이다.
직경 붕괴 (Diameter Collapse): 핵심 통찰은 증강된 상호작용 그래프의 직경이 $\text{diam}(G_{int}) \leq (q+1)p$ 를 만족하면, 라이트콘이 전체 그래프를 덮는다는 것이다. 이는 얕은 깊이에서 먼 노드들이 도달 불가능해지는 "인과적 장애(causal obstruction)"를 제거한다.

그래프 증강 문제

저자들은 지름길 설계를 **유계 직경 그래프 증강 문제(bounded-diameter graph augmentation problem)**로 공식화한다: 즉, $\text{diam}(V, E \cup E_{new}) \leq D$ 를 만족하는 최소 에지 집합 $E_{new}$ 를 찾는 것이다 (여기서 $D$ 는 목표 직경이며, 일반적으로 $2p$ 또는 $(q+1)p$ 이다). 이들은 이 그래프 이론적 문제의 최적해가 주어진 깊이 $p$ 에 대해 직경 기반의 인과적 장애를 정확히 제거함을 증명한다.

3. 주요 기여

상호작용 그래프 기하로서의 국소성: 본 논문은 QAOA의 한계를 알고리즘 자체의 고유한 특성이 아니라, 알고리즘의 상호작용 그래프의 기하학적 특성으로 재정의한다. 비용 함수 $H_C$ 를 고정한 채 믹서 기하 구조를 수정함으로써 국소성 제약을 극복할 수 있음을 보여준다.
수송 증강 믹서: 최적화 목적을 변경하지 않으면서 수송 채널 역할을 하는 지름길 수송 믹서(Commuting XX 및 Scheduled XX + YY)를 도입한다.
정확한 유한 깊이 라이트콘 재귀: 정확한 서포트 성장 맵( $\Phi_p$ 및 $\Psi_q$ )과 하이젠베르크 진화된 관측값의 명시적 반경 경계를 도출한다. 여기에는 전체 라이트콘 기준과 곱 연산 초기 상태(product initial states)에 대한 교환자 기반 장애가 포함된다.
직경 붕괴로서의 지름길 배치: 지름길 설계를 그래프 증강 문제로 전환한다. 논문은 $p$ 깊이에서 인과적 장애를 제거하기 위해 필요한 최소 추가 에지 수가 최적의 $2p$ -증강(diameter- $2p$ augmentation)에 해당함을 증명한다.
벤치마크 및 스케일링: 다각도 QAOA(multi-angle QAOA, ma-QAOA)와의 구조적 분리를 보여주는 수치적 증거를 제시한다. 고직경 그래프에서 ma-QAOA의 성능은 시스템 크기에 따라 저하되는 반면, 수송 안사츠(transport ansatz)는 유효 상호작용 직경이 붕괴되면 **크기 불변성(size-invariant)**을 보인다.

4. 실험 결과

저자들은 세 가지 그래프 패밀리(균일한 랜덤 4-정규 그래프, 연결된 이분 그래프, 랜덤 트리)에 대해 정확한 상태 벡터 시뮬레이션(Qiskit의 AerSimulator 사용)을 수행했다.

이분 그래프 (기본 직경 4):
- 깊이 $p=1$ 에서, 스케줄링된 XX + YY 믹서를 사용하여 상호작용 직경을 $d=1$ 로 줄였을 때, 앙상블 평균 근사 비율(AR)이 ma-QAOA의 0.7378에서 0.9767로 증가했다.
- 성능 곡선은 9개의 서로 다른 시스템 크기에 대해 거의 평탄하게 나타났으며, 이는 시스템 크기가 아닌 직경이 제한 요소였음을 나타낸다.
랜덤 트리 (기본 직경 10):
- 깊이 $p=2$ 에서, 직경을 $d=1$ 로 줄이면 AR이 0.9226에서 0.9997로 향상되었다.
- 중간 단계의 직경 감소(예: $d=3$ 또는 $4$) 역시 베이스라인 대비 상당한 개선을 보여주었다.
4-정규 그래프 (기본 직경 3-4):
- 기본 직경이 작음에도 불구하고, 상호작용 직경을 $d=1$ 로 붕괴시키면 $p=1$ 에서 완벽에 가까운 성능(AR $\approx$ 0.997)을 달im였다.

5. 의의 및 주장

본 논문은 희소 그래프에서 얕은 QAOA의 주요 제한 사항이 **그래프 거리 장애(graph-distance obstruction)**라고 주장한다. 믹서를 설계 가능한 수송 기하 구조로 취급함으로써, 저자들은 비용 함수를 변경하지 않고도 회로의 인과적 라이트콘을 "재배선(rewire)"할 수 있는 원칙적인 방법을 제공한다.

신중한 주장: 저자들은 자신들의 엄격한 결과가 "보편적인 최적화 개선에 대한 주장이 아니라 인과적이고 그래프 이론적인 것"임을 명시한다. 이 방법이 모든 인스턴스에 대해 전역 최적해로의 수렴을 보장한다고 주장하는 것이 아니라, 얕은 QA로 인해 발생하는 먼 거리의 그래프 특징에 대한 구조적 맹목성을 제거한다는 점을 강조한다.
의의: 본 연구는 성능이 시스템 크기가 아니라 달성된 상호작용 직경에 의해 주로 제어된다는 점을 확립한다. 직경이 붕괴되면 수송 안사츠는 크기 불변적인 최적 성능에 도달하며, 이는 고직경 문제에 대한 얕은 깊이의 변분 양자 알고리즘을 위한 확장 가능한 경로를 제공한다.

논문은 향-연구에서 더 풍부한 수송 해밀토니안이나 다른 QAOA 변형(예: warm-start, RQAOA)과의 결합을 탐구할 수 있음을 언급하며, 현재의 수송 증강 프레임워크가 국소성 병목 현상을 극복하기 위한 견고한 이론적 및 경험적 토대를 제공한다고 결론짓는다.

Dealing with locality in QAOA