기술 요약: 분할 정복형 QAOA를 위한 적응형 큐비트 프리징(Adaptive Qubit Freezing) 기반의 강건한 그래프 분할

1. 문제 정의

양자 근사 최적화 알고리즘(QAOA)은 MaxCut과 같은 조합 최적화 문제를 해결하기 위한 선도적인 하이브리드 양자-고전 접근 방식입니다. 그러나 노이즈가 있는 중규모 양자(NISQ) 장치에서의 적용은 제한된 큐비트 레지스터와 노이즈 누적에 의해 제약을 받습니다. 분할 정복형 QAOA(DC-QAOA)는 큰 문제 그래프를 하드웨어 예산 내에 들어오는 작은 서브그래프로 분해하여 개별적으로 해결한 뒤 전역 솔루션을 재구성함으로써 이 문제를 해결합니다.

기존 DC-QAOA 프레임워크의 핵심 병목 구간은 **분해 단계(decomposition stage)**입니다. 대형 그래프 분할(LGP)과 같은 표준 방식은 그래프를 두 개의 독립적인 구성 요소로 분리하기 위해 제거되는 작은 정점 분리자(vertex separator)에 의존합니다. 이러한 가정은 밀집된 그래프(예: 밀집된 Erdős–Rényi, 높은 부착도를 가진 Barabási–Albert, 또는 완전 그래프)에서는 치명적으로 실패합니다. 이러한 그래프에서는 소수의 노드를 제거하는 것만으로는 네트워크를 절단할 수 없기 때문입니다. 이러한 경우, 표준 DC-QAOA 파이프라인은 차선책조차 제시하지 못한 채 완전히 중단되어 솔루션을 반환하지 못합니다. 기존의 전체 커버리지(full-coverage) 대안들은 재구성 충실도를 희생하거나 과도한 고전적 오버헤드를 초래합니다.

2. 방법론: FrozenLGP

저자들은 분할 가능성을 구조적 가정이 아닌 강제 가능한 속성으로 변환하는 적응형 분해 프레임워크인 **Frozen Large Graph Partitioning (FrozenLGP)**을 제안합니다. 이 방법은 세 단계의 파이프라인을 통해 작동합니다.

단계 1: 표준 LGP

알고리즘은 먼저 표준 정점 분리자 분할을 시도합니다. 만약 교차하는 에지 없이 그래프를 두 개의 구성 요소로 나누는 유효한 분리자가 존재한다면, 파이프라인은 추가 오버헤드 없이 표준 DC-QAOA와 동일하게 진행됩니다.

단계 2: 적응형 큐비트 프리징 (Adaptive Qubit Freezing)

표준 분할이 실패할 경우(즉, 크기가 $k-1$ 이하인 분리자가 존재하지 않을 때), FrozenLGP는 적응형 프리징 메커니즘을 활성화합니다.

1. 최소 정점 컷(Minimum Vertex Cut, MVC) 계산: 후보 분리자 $S$에 대해, 알고리즘은 노드 분할 보조 네트워크 상의 max-flow 정식화를 사용하여 잔여 그래프 $G \setminus S$의 최소 정점 컷 $F$를 계산합니다. 이는 이분 분할을 방해하는 "방해" 정점들의 최소 집합을 식별합니다.
2. 고전적 프리징(Classical Freezing): 정점 $F$의 상태는 결정론적인 스핀($+1$ 또는 $-1$)으로 고전적으로 고정됩니다.
3. 바이어스 폴딩(Bias Folding): 프리징된 노드와 연결된 에지의 에너지 기여도는 버려지지 않습니다. 대신, 이들은 Ising 해밀토니안에서 인접한 활성 큐비트에 적용되는 선형 바이어스 항($h_i$)으로 수학적으로 폴딩됩니다. 이는 프리징된 노드와 관련된 얽힘 게이트(entangling gates)를 제거하면서도 비용 함수의 엄밀한 정의를 보존합니다.
4. 서브 회로 실행: 이제 이분 분할이 가능해진 잔여 활성 그래프는 수정된 해밀토니안을 사용하여 증강된 QAOA 회로로 해결됩니다.

단계 3: 연결성 보존 분할 (Connectivity-Preserving Partitioning, CPP)

최소 컷을 프리징하는 것(예: 완전 그래프 $K_n$의 경우)이 여전히 유효한 분할을 생성하지 못할 경우(예: 프리징 예산 $B_f$ 내에서), 결정론적 폴백(fallback)이 호출됩니다. CPP는 정렬된 정점 리스트를 중간 지점에서 분할하여 단일 경계 노드를 공유하는 두 개의 서브그래프를 생성합니다. 교차 분할 에지는 양자 회로에서는 제외되지만 고전적으로 추적됩니다. 최종 솔루션은 버려진 에지의 고전적 기여도를 바탕으로 양자 출력 분포를 재점수화(rescoring)하여 재구성되며, 이를 통해 100% 커버리지를 보장합니다.

3. 주요 기여

1. 정확하고 예산 인식적인 분해: FrozenLGP는 분할을 가능하게 하기 위해 방해하는 정점의 수를 증명 가능한 최소치(MVC를 통해)만큼 프리징합니다. 이 최소성은 서브 회로 해밀토니안에 도입되는 왜곡을 제한하며, 위상 예측 기반의 날카로운 회복 임계값($B_f = \kappa - (k-1)$, 여기서 $\kappa$는 정점 연결도)을 설정합니다.
2. 무조건적 커버리지 하한: CPP 폴백을 통합함으로써, 이 프레임워크는 정점 제거 전략이 근본적으로 실패하는 위상(예: 완전 그래프)을 포함한 모든 그래프 토폴로지에 대해 100%의 분해 커버리지를 보장합니다.
3. NISQ 강건성: 고차수 "핫스팟(hotspot)" 노드를 프리징함으로써, 이 방법은 필요한 2-큐비트 얽힘 게이트(CNOT) 및 회로 깊이를 줄입니다. 이는 게이트 에러와 결맞음(decoherence)에 대한 노출을 줄여, 노이즈가 있는 환경에서 개선된 강건성을 제공합니다.

4. 실험 결과

저자들은 $n=10,000$까지의 다양한 그래프 크기와 토폴로지(Barabási–Albert, Erdős–Rényi, 무작위 d-regular)에 대해 FrozenLGP를 평가했습니다.

• 분해 커버리지: 표준 DC-QAOA 베이스라인이 단 **4.6%**의 커버리지만 달성한 고연결성 인스턴스에서, FrozenLGP는 **100%**의 커버리지를 달성했습니다.
• 예산 임계값: 실험을 통해 유효성 회복의 급격한 전이를 확인했습니다. 무작위 d-regular 그래프의 경우, 프리즈 예산이 $B_f \ge d - (k-1)$을 만족할 때 정확히 완전한 회복이 이루어졌습니다.
• 솔루션 품질:
  • 보존성: 표준 DC-QAOA로 해결 가능한 인스턴스에서, FrozenLGP(with $B_f=3$)는 통계적으로 구별 불가능한 근사 비율(AR)을 생성했습니다(예: 공통 세트에서 AR 0.988 vs 0.983). 이는 성능 저하가 없음을 확인시켜 줍니다.
  • 확장성: 이전에 지원되지 않던 밀집 그래프에서, FrozenLGP는 높은 근사 비율(AR $\approx 0.98$)을 유지하며, 컷 에지 손실(cut-edge losses)로 인해 낮은 성능(예: $n=100$에서 AR $\approx 0.76$)을 보인 대안적인 전체 커버리지 전략인 QAOA-in-QAOA(QAOA2)를 크게 능가했습니다.
• 효율성: 전처리 시간은 무시할 수 있는 수준(초 단위)이었으며, 표준 분할이 성공한 그래프에서는 프리징에 따른 오버헤드가 발생하지 않았습니다.

5. 의의 및 주장

본 논문은 FrozenLGP가 근사 미래 하드웨어를 위한 **토폴로지 강건한 프런트 엔드(topology-robust front end)**를 구축한다고 주장합니다. 이 연구의 주요 의의는 분할 정복형 접근 방식의 "구조적 실패 모드"를 제거했다는 점에 있습니다. 분할 가능성을 전제 조건이 아닌 강제 가능한 속성으로 취급함으로써, 이 방법은 분해 기반 전략이 접근할 수 없었던 밀집되고 고도로 연결된 그래프로 QAOA의 적용 범위를 확장합니다.

저자들은 이 접근 방식이 단순히 커버리지를 확장하는 것이 아니라, 분리자 구조를 보존하고 컷 에지 에러의 누적을 피함으로써 밀집 그래프에서 임의의 분할 방법(QAOA2와 같은)보다 더 높은 솔루션 품질을 유지한다고 강조합니다. 또한, 큐비트 프리징을 통한 얽힘 게이트의 감소는 NISQ 장치의 노이즈를 완화하기 위한 실질적인 경로를 제공합니다. 결론적으로 FrozenLGP는 이론적 QAOA 역량과 현재의 양자 하드웨어 제약 사이의 간극을 메우는 확장 가능하고 구조적으로 강건한 솔루션을 제공합니다.